[HDU2433] Travel BFS+最短路生成树

题目意思是有n个点,m条边,对于每一条边,求出删去它后各点之间的最短路总和,若删去后图不连通,则输出-1。

刚开始当然想到暴力,于是枚举删去哪条边,然后BFS一下,复杂度为 O(mn(n+m)) ,大的数据直接TLE了。换个思路,删去一条边,并不是所有点与点之间的最短路都会变,而仅仅只有两点间的最短路径包括这条边时才可能改变最短路,故我们可以先将以 i(i∈[1,n]) 为起点,造出最短路生成树,然后判定各条边是否在这棵树上,如果在路径上,就删去该边BFS一次,由于每次求出的最短路生成树的边只有n-1条,故复杂度为 O(n2(n+m)) ,这样刚刚好,接下来就是实现了。由于存在重边,因此在存边的时候我们最好同时存上边的编号,这样在BFS时只要判一下边的编号就行了,很方便。至于如何判断最短路生成树有无经过一条边,我们可以在BFS过程中mark一下路径,于是一个个问题就迎刃而解了。

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iostream>
#define M 105
using namespace std;
template <class T>
inline void Rd(T &res){
char c;res=0;int k=1;
while(c=getchar(),c<48&&c!='-');
if(c=='-'){k=-1;c='0';}
do{
res=(res<<3)+(res<<1)+(c^48);
}while(c=getchar(),c>=48);
res*=k;
}
typedef pair<int,int> P;
vector<P>G[M];
struct edge{
int u,v;
}e[2005];
struct node{
int pos,step;
}Q[M];
int n,m,dis[M],used[M],mark[M][M],res[2005],cnt[M][M],degree[M];
void BFS(int x,int t){
memset(dis,-1,sizeof(dis));//初始化dis,其实不需要,是为了调试的时候好看
memset(used,0,sizeof(used));
int L=0,R=0;
node st;
st.pos=x,st.step=0;
dis[x]=0;
used[x]=1;
Q[R++]=st;
while(L<R){
node now=Q[L++];
for(int i=0;i<G[now.pos].size();i++){
int k=G[now.pos][i].first;
int id=G[now.pos][i].second;
if(!used[k]&&id!=t){
used[k]=1;
mark[now.pos][k]=mark[k][now.pos]=1;
node nxt;
nxt.pos=k;
nxt.step=now.step+1;
dis[k]=nxt.step;
Q[R++]=nxt;
}
}
}
}
int main(){
int u,v;
Rd(n);Rd(m);
for(int i=1;i<=m;i++){
Rd(u);Rd(v);
e[i].u=u;e[i].v=v;
cnt[u][v]++;cnt[v][u]++;
degree[u]++;degree[v]++;
G[u].push_back(P(v,i));
G[v].push_back(P(u,i));
}
for(int i=1;i<=n;i++){
int sum=0;
memset(mark,0,sizeof(mark));
BFS(i,0);
for(int j=1;j<=n;j++)sum+=dis[j];
for(int j=1;j<=m;j++){
if(res[j]==-1)continue;
if(degree[e[j].u]==1||degree[e[j].v]==1){res[j]=-1;continue;}
if(!mark[e[j].u][e[j].v]||cnt[e[j].u][e[j].v]>1){
res[j]+=sum;
}
else{
BFS(i,j);
for(int k=1;k<=n;k++){
if(!used[k]){res[j]=-1;break;}
res[j]+=dis[k];
}
}
}
}
for(int i=1;i<=m;i++)printf("%dn",res[i]);
return 0;
}

最后

以上就是端庄野狼为你收集整理的[HDU2433] Travel BFS+最短路生成树的全部内容，希望文章能够帮你解决[HDU2433] Travel BFS+最短路生成树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。