UVALive 4080 最短路树

题意

给N个点，M条边，如果两个点之间没有边，则默认为l。问所有点两两之间最短路之和是多少。然后删除一条边，问删除某一条边后最大是多少。

题解

这道题第一问可以很简单用Floyd算法求解。但是第二问如果使用Floyd算法，就会存在超时的问题。贪心上也没有比较好的策略，因此考虑使用最短路算法暴力枚举。但是由于暴力枚举可能超时，因此引入最短路树的概念。最短路树就是一个点到其他所有点的最短路所形成的树。 在使用最短路算法松弛的时候记录一下前置节点，就可以轻而易举的得到最短路树。然后对于暴力求解的过程，如果我们删除的边不在最短路上，那么最短路将不会重新计算。这样整体的复杂度就会变成O(N^2*M*log(N))，这个时间复杂度刚好足够。

注意事项

需要注意的是，这道题存在重边的情况，对于重边，如果删除一条边，则会采用其他边顶替。这一点在处理的时候需要特别注意。

代码

#include <bits/stdc++.h> #define LL long long #define UP(i,l,h) for(int i=l;i<h;i++) #define DOWN(i,h,l) for(int i=h-1;i>=l;i--) #define W(t) while(t) #define MEM(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MAXN 210 #define COUT(x) cout<<x<<endl #define int LL using namespace std; int dis[MAXN][MAXN]; int n,m,l; struct Node { int u,d; bool operator < (const Node v) const { return d>v.d; } Node(int u,int d):u(u),d(d) {} }; bool vis[MAXN]; int d[MAXN],p[MAXN]; int dijkstra(int u) { MEM(vis,0); UP(i,0,n) d[i]=l; MEM(p,-1); priority_queue<Node> q; q.push(Node(u,0)); d[u]=0; W(!q.empty()) { int x=q.top().u; q.pop(); if(vis[x]) continue; vis[x]=true; UP(i,0,n) { if(d[x]+dis[x][i]<d[i]) { d[i]=d[x]+dis[x][i]; p[i]=x; q.push(Node(i,d[i])); } } } int sum=0; UP(i,0,n) { sum+=d[i]; } return sum; } int ans[MAXN]; bool tree[MAXN][MAXN]; bool inTree[MAXN][4050]; struct Edge { int u,v,w; Edge(int u,int v,int w):u(u),v(v),w(w) {} }; vector<Edge> edges; int sec[MAXN][MAXN]; main() { // freopen("d:/in.txt","r",stdin); // freopen("d:/o1.txt","w",stdout); W(~scanf("%lld%lld%lld",&n,&m,&l)) { edges.clear(); int a,b,s; UP(i,0,n) { UP(j,0,n) { dis[i][j]=sec[i][j]=(i==j?0:l); // COUT(dis[i][j]<<" "<<i<<" "<<j); } } UP(i,0,m) { scanf("%lld%lld%lld",&a,&b,&s); if(dis[a-1][b-1]>=s) { sec[a-1][b-1]=sec[b-1][a-1]=min(sec[b-1][a-1],dis[b-1][a-1]); // COUT("sec "<<sec[a-1][b-1]<<" "<<a-1<<" "<<b-1); dis[a-1][b-1]=dis[b-1][a-1]=s; }else{ sec[a-1][b-1]=sec[b-1][a-1]=min(sec[b-1][a-1],s); } edges.push_back(Edge(a-1,b-1,s)); } MEM(inTree,false); UP(i,0,n) { ans[i]=dijkstra(i); // COUT(ans[i]); MEM(tree,false); UP(j,0,n) { if(p[j]!=-1) tree[p[j]][j]=tree[j][p[j]]=true; } UP(j,0,m) { if(tree[edges[j].u][edges[j].v]) { inTree[i][j]=true; } } } int temp1=0; UP(i,0,n) temp1+=ans[i]; int temp2=temp1; UP(i,0,m) { if(dis[edges[i].u][edges[i].v]!=edges[i].w) continue; int temp3=0; int distemp=dis[edges[i].u][edges[i].v]=dis[edges[i].v][edges[i].u]; dis[edges[i].u][edges[i].v]=dis[edges[i].v][edges[i].u]=sec[edges[i].v][edges[i].u]; UP(j,0,n) { if(inTree[j][i]) temp3+=dijkstra(j); else temp3+=ans[j]; } dis[edges[i].u][edges[i].v]=dis[edges[i].v][edges[i].u]=distemp; // COUT(temp3); temp2=max(temp2,temp3); } printf("%lld %lld\n",temp1,temp2); } }