首页 > 代码库 > LA 4080 (多源最短路径+边修改+最短路径树）
LA 4080 (多源最短路径+边修改+最短路径树）
题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=32266
题目大意：①先求任意两点间的最短路径累加和，其中不连通的边权为L ②删除任意一条边,求全局最短路径和的最大值。
解题思路：
首先说下多源最短路中，floyd和和优先队列优化的dijkstra的取舍。floyd比较好拍，dijkstra具有常数有势，以及灵活性（如求第二问的时候）。
本题最烦人的是枚举删除一条边，按照正常思维，要重新做n次dijkstra，复杂度已经到了可怕的(n*m^2*logn),那么是否有必要每次修改一条边的时候，全源重新做一次最短路呢？
答案是否定的。只要构建一颗最短路径树即可。
不要被名字唬住，其实就是一个二维数组，belong[边id][s点]，即初次做全源Dijkstra的时候，为每条边进行标记，标记内容为本次dij的s点。
注意这里的边指的是输入边id，不是图中的边（这题是无向图，输入边被add了两次）。
枚举删除边时，如果belong[边id][s点]=true,则说明这条边与这次的单源dij有关，必须重新dij。如果为false，则无关，值还是初次做dij的值。
标记belong的方法：在每次优先队列出队的时候，对出队点所在的入队前的边进行标记，具体方法是开一个p数组，每次Relax的时候，记录一下Relax的边即可。之后入队在取出，p数组就能立刻取出入队前的边了。
本题存在重边，不支持的重边的数据结构注意了，尤其是邻接表。推荐链式前向星。
另外两个问的结果都超过了int32。
#include "cstdio"#include "queue"#include "cstring"using namespace std;#define maxn 155#define maxp 2005#define inf 1<<28#define LL long longstruct Edge{ int next,to,d,id;}e[maxp*2];struct status{ int d,p; status(int d,int p):d(d),p(p) {} bool operator < (const status &a) const {return d > a.d;}};int n,m,l,tol,head[maxn],d[maxn],p[maxn],dis[maxn][maxn];LL ans1,ans2,w[maxn];bool vis[maxn],belong[maxp][maxn],del[maxp];void addedge(int u,int v,int c,int id){ e[tol].id=id; e[tol].d=c; e[tol].to=v; e[tol].next=head[u]; head[u]=tol++;}void dijkstra1(int s){ memset(vis,false,sizeof(vis)); memset(p,0,sizeof(p)); for(int i=1;i<=n;i++) d[i]=(i==s?0:inf); priority_queue<status> Q; Q.push(status(0,s)); while(!Q.empty()) { status tt=Q.top();Q.pop(); int x=tt.p; if(vis[x]) continue; vis[x]=true; belong[p[x]][s]=true; for(int i=head[x];i!=-1;i=e[i].next) { int v=e[i].to; if(d[x]+e[i].d<d[v]) { p[v]=e[i].id; d[v]=d[x]+e[i].d; Q.push(status(d[v],v)); } } } for(int i=1;i<=n;i++) { if(d[i]==inf) { ans1+=l; w[s]+=l; } else { ans1+=d[i]; w[s]+=d[i]; } }}LL dijkstra2(int s){ memset(vis,false,sizeof(vis)); for(int i=1; i<=n; i++) d[i]=(i==s?0:inf); priority_queue<status> Q; Q.push(status(0,s)); while(!Q.empty()) { status tt=Q.top(); Q.pop(); int x=tt.p; if(vis[x]) continue; vis[x]=true; for(int i=head[x]; i!=-1; i=e[i].next) { if(del[e[i].id]) continue; //标记为删除的边跳过 int v=e[i].to; if(d[x]+e[i].d<d[v]) { d[v]=d[x]+e[i].d; Q.push(status(d[v],v)); } } } long long tt=0; for(int i=1; i<=n; i++) { if(d[i]==inf) tt+=l; else tt+=d[i]; } return tt;}int main(){ int u,v,c; while(scanf("%d%d%d",&n,&m,&l)!=EOF) { memset(head,-1,sizeof(head)); memset(belong,false,sizeof(belong)); memset(del,false,sizeof(del)); memset(w,0,sizeof(w)); tol=ans1=ans2=0; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&c); addedge(u,v,c,i); addedge(v,u,c,i); } for(int i=1;i<=n;i++) dijkstra1(i); for(int i=1;i<=m;i++) { LL tt=0; del[i]=true; for(int j=1;j<=n;j++) if(belong[i][j]) tt+=dijkstra2(j); else tt+=w[j]; del[i]=false; ans2=max(ans2,tt); } printf("%lld %lld\n",ans1,ans2); }}
2814660 | neopenx | UVALive 4080 | Accepted | 0 KB | 409 ms | C++ 4.5.3 | 2990 B | 2014-10-04 18:34:44 |
LA 4080 (多源最短路径+边修改+最短路径树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。