hdu2433 Travel(枚举/最短路删边+bfs)

题目

n(n<=100)个点，m(m<=3e3)条边，

1-m条边，第i次独立在原图中删掉第i条边，

问删掉这一条边之后，所有点对(i,j)之间的最短路之和的值是多少

如果有一对不连通，输出-1

思路来源

https://blog.csdn.net/a709743744/article/details/51559569

https://blog.csdn.net/Todobe/article/details/73250646

题解

先处理出每一个点的最短路径树，used[i][j][k]标记在以i为单源的最短路中，j-k这条边是最短路径树上的边

删掉每一条边之后，枚举每一个点作为源点，如果删掉的这条边不是该点的最短路径树上的边，

那就直接加上预处理出的答案，如果是，就重新跑一遍最短路。

只有当一条边在最短路径树上时会重新计算，

每棵最短路径树有n条边，有n棵最小路径树，

所以一共会重新计算n*n次。时间复杂度O(n*n*m)

bfs的复杂度，

如果用链式前向星+标记是否被删的话，是O(m)的，总的是O(n^2*m)

如果用矩阵存，是否连通，每次检查n个点，是O(n*n)的，总的是O(n^4)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=105;
const int M=3005;
struct edge{int u,v;}e[M];
int mp[N][N],dis[N];
int ans,sum[N],tmp,v;
bool used[N][N][N],vis[N],ok;
int n,m;
int bfs(int s,int op)
{
	memset(vis,0,sizeof vis);
	memset(dis,0,sizeof dis);
	queue<int>q;
	q.push(s);
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=1;i<=n;++i)
		{
			if(vis[i])continue;
			if(!mp[u][i]&&!mp[i][u])continue;//没边 
			vis[i]=1;
			if(op==0)used[s][u][i]=used[s][i][u]=1;
			dis[i]=dis[u]+1;
			q.push(i);
		}
	}
	int tot=0;
	for(int i=1;i<=n;++i)
	{
		if(i==s)continue;
	 	if(!dis[i])return -1;//不连通
		tot+=dis[i];
	}
	return tot;
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		memset(mp,0,sizeof mp);
		memset(used,0,sizeof used);
		for(int i=1;i<=m;++i)
		{
			scanf("%d%d",&e[i].u,&e[i].v);
			mp[e[i].u][e[i].v]++;
			mp[e[i].v][e[i].u]++;
		}
		ok=1;ans=0;
		for(int i=1;i<=n&&ok;++i)
		{
			sum[i]=bfs(i,0);
			if(sum[i]==-1)ok=0;
			else ans+=sum[i];
		}
		for(int i=1;i<=m;++i)
		{
			mp[e[i].u][e[i].v]--;
			mp[e[i].v][e[i].u]--;
			if(!ok)puts("INF");
			else if(mp[e[i].u][e[i].v])printf("%d\n",ans);
			else
			{
			tmp=ans;
			bool flag=1;
			for(int j=1;j<=n;++j)
			{
				if(used[j][e[i].u][e[i].v])
				{
					tmp-=sum[j];
					int now=bfs(j,1);
					if(now==-1)
					{
						flag=0;
						break;
					}
					tmp+=now;
				}
			}
			if(!flag)puts("INF");
			else printf("%d\n",tmp);
			}
			mp[e[i].u][e[i].v]++;
			mp[e[i].v][e[i].u]++;
		}
	}
	return 0;
}