这个题在bzoj上好像是个权限题,想做的可以去Vani的博客下载测试数据。
这里有题面。
简单叙述一下题意:
给你一个n个点、m条边的带权无向图,S点和T点,询问Q次删一条给定的边的S-T最短路。
其中 1<=n,m,q<=200000
。
ps. 1.这个题网上好多解法都是错的。2.这个题数据范围很大。
先求S到每个点的距离ds[i]
。如果ds[T]为inf的话,输出Q个无解好了。
然后再求每个点到T的距离dt[i]
。(用堆优化的Dijkstra即可。)
建一张最短路径图Gs仅包含ds[v]==ds[u]+w[u,v]
这样的有向边。
同理再建一张最短路径图Gt仅包含dt[v]==dt[u]+w[u,v]
这样的有向边。
我们可以发现在这两张最短路径图上,有一些关键边,与桥边类似,从S-T的最短路必经这些边。
可以知道,如果删掉的不是这些关键边,那么答案不会变,只有删掉关键边答案才会变。
这些关键边如何求呢?网上有些题解写的是把最短路径图看成无向图的桥边。(这个是有明显反例的,随便一拍都是反例,但是有的代码就是能过题 - -|)
还有的是用对Tarjan求桥边的时候做了一些限制,但是我觉得正确性未知。
我用了一种比较保(qi)险(guai)的方法,求出的这些关键边。
首先假设每条边的容量都是1,像网络流一样做两次增广,注意不需完整的最大流,只需两次增广。
如果流量>=2
,说明这个图里没有关键边,直接输出Q个ds[T]
即可。
那么我们来看流量是1的时候,很显然关键边就是能成为最小割的边(流量只有1),我们用Tarjan对这个图求一次强连通分量,设id[i]
表示i这个点所属的连通分量编号。如果一条边(u,v)
满流且id[u]!=id[v]
那么这条边就可以成为最小割的一条边,即为关键边。
如果把Gs
中的关键边反向就是Gt
中的关键边。
我们就得到了Gs
与Gt
中的关键边,这些关键边应该从S到T排成一列,不妨编号为1,2,3...。
我们考虑删除一条关键边(u,v)
,如果另一条非最短路图上的边(x,y)
跨越了(u,v)
那么ds[x]+w[x,y]+dt[y]
就可能成为答案,这些(x,y)
取min即可。
现在需要判断那些(x,y)
可以跨越(u,v)
,有用了一种稳(qi)妥(guai)的方法判断的,将Gs
,Gt
中的边都给一个权值,如果这条边是关键边,那么这条边边权为1,否则这条边边权为0,然后我们在Gs
上求一个这个图的最短路记为Ds[i]
,同理Dt[i]
,注意这里不用Dijkstra或SPFA,因为边权都是0/1所以来一次0/1 bfs即可(双端队列)。
Ds[i]
与Dt[i]
的意义比较明显,从S到i点最短路经过最少关键边的数量,和从i点到T点最短路经过最少关键边的数量。那么我们就可以判断一条边是否跨过了第num
条关键边,即为Ds[x]<num&&Dt[y]<sum-num
(sum
为关键边总数)。
但是每次枚举所以的边是不可能的,我们可以用离线的思想,预处理出每条关键边的答案。先预处理出Ds[i]
值相等的点,可以存进一个vector。然后我们从左向右扫描这些关键边,从左向右扫描时,右端合法状态(Dt[y]
)是单调递减的,所以可以维护一个小根堆,代表现在可行的决策,堆中的关键字为ds[x]+w[x,y]+dt[y]
,那么堆顶就是一个最优方案。具体的讲,现在准备算第num
条关键边,先把堆顶中Dt[y]>=sum-num
的边删去,然后添加vector中Ds[i]==num
的所有点的所有出边入堆,然后记录堆顶答案,算下一个num。
然后读入询问判一下是哪条边,输出答案即可。
程序写了不到6k。程序中变量名称对应题解中变量名称。
代码很丑。
/************************************************************** Problem: 2725 User: zrts Language: C++ Result: Accepted Time:13512 ms Memory:49700 kb ****************************************************************/ #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cstdio> #include<queue> #include<vector> //by zrt //problem: using namespace std; typedef long long LL; const LL inf(0x3f3f3f3f3f3f3f3fLL); ); ],X0[],P0[],tot0,E0[]; void add0(int x,int y,int z){ P0[++tot0]=y;X0[tot0]=H0[x];H0[x]=tot0;E0[tot0]=z; } ],X1[],P1[],tot1,flow[],],E1[]; void add1(int x,int y,int z){ P1[++tot1]=y;X1[tot1]=H1[x];H1[x]=tot1;flow[tot1]=z;from[tot1]=x; } ],X2[],P2[],tot2,E2[],from2[]; void add2(int x,int y,int z){ P2[++tot2]=y;X2[tot2]=H2[x];H2[x]=tot2;E2[tot2]=z;from2[tot2]=x; } int n,m,Q,S,T; ]; LL ds[],dt[]; ]; struct N{ int x;LL w; N(,LL b=){ x=a,w=b; } friend bool operator < (N a,N b){ return a.w>b.w; } }; priority_queue<N> q; ]; queue<int> qu; deque<int> dq; bool bfs(){ memset(d,,sizeof d); d[S]=;int x;qu.push(S); while(!qu.empty()){ x=qu.front();qu.pop(); if(x==T) continue; for(int i=H1[x];i;i=X1[i]){ &&!d[P1[i]]){ d[P1[i]] =d[x]+; qu.push(P1[i]); } } } return d[T]; } int dfs(int x,int a){ ) return a; int tmp,f=a; for(int i=H1[x];i;i=X1[i]){ &&d[P1[i]]==d[x]+){ tmp=dfs(P1[i],min(flow[i],a)); a-=tmp; flow[i]-=tmp; flow[i^]+=tmp; if(!a) break; } } ; return f-a; } int ff; ],tim; ],top; ]; ]; int cnt; void tarjan(int x){ stk[top++]=x;instk[x]=; int dfn=low[x]=++tim; for(int i=H1[x];i;i=X1[i]){ ) continue; if(!low[P1[i]]){ tarjan(P1[i]); low[x]=min(low[x],low[P1[i]]); }else if(instk[P1[i]]) low[x]=min(low[x],low[P1[i]]); } if(dfn==low[x]){ cnt++; int k; do{ k=stk[--top]; instk[k]=; id[k]=cnt; }while(k!=x); } } ],Dt[]; LL ans[]; vector<]; struct A{ int x,y; LL w; A(,,LL c=){ x=a,y=b,w=c; } friend bool operator < (A a,A b){ return a.w>b.w; } }; priority_queue<A> pq; int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif tot0=tot1=; scanf("%d%d",&n,&m); ,x,y,z;i<m;i++){ scanf("%d%d%d",&x,&y,&z); add0(x,y,z); add0(y,x,z); } scanf("%d%d%d",&S,&T,&Q); memset(ds,0x3f,sizeof ds);memset(dt,0x3f,sizeof dt); ds[S]=dt[T]=;int x; q.push(N(S,)); while(!q.empty()){ x=q.top().x; q.pop(); if(vis[x]) continue; vis[x]=; if(x==T) continue;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1 for(int i=H0[x];i;i=X0[i]){ if(!vis[P0[i]]&&ds[P0[i]]>ds[x]+E0[i]){ ds[P0[i]]=ds[x]+E0[i]; q.push(N(P0[i],ds[P0[i]])); } } } memset(vis,,sizeof vis); q.push(N(T,)); while(!q.empty()){ x=q.top().x;q.pop(); if(vis[x]) continue; vis[x]=; if(x==S) continue;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1 for(int i=H0[x];i;i=X0[i]){ if(!vis[P0[i]]&&dt[P0[i]]>dt[x]+E0[i]){ dt[P0[i]]=dt[x]+E0[i]; q.push(N(P0[i],dt[P0[i]])); } } } if(ds[T]==inf) { ;i<Q;i++){ puts("Infinity"); } goto ed; } ;i<=n;i++){ for(int j=H0[i];j;j=X0[j]){ if(ds[P0[j]]==ds[i]+E0[j]){ add1(i,P0[j],); add1(P0[j],i,); } if(dt[P0[j]]==dt[i]+E0[j]){ add2(i,P0[j],); } } } ff=; ); ); ){ ;i<Q;i++) printf("%lld\n",ds[T]); goto ed; } ;i<=n;i++) if(!low[i]) tarjan(i); ;i<=tot1;i+=){ &&id[; } ;i<=tot2;i++){ ; } memset(vis,,sizeof vis); memset(Ds,0x3f,sizeof Ds); memset(Dt,0x3f,sizeof Dt); Ds[S]=Dt[T]=; dq.push_back(S); while(!dq.empty()){ x=dq.front();dq.pop_front(); if(vis[x]) continue; vis[x]=; for(int i=H1[x];i;i=X1[i]){ ) continue; Ds[P1[i]]=min(Ds[P1[i]],Ds[x]+E1[i]); if(E1[i]){ dq.push_back(P1[i]); }else dq.push_front(P1[i]); } } memset(vis,,sizeof vis); dq.push_back(T); while(!dq.empty()){ x=dq.front();dq.pop_front(); if(vis[x]) continue; vis[x]=; for(int i=H2[x];i;i=X2[i]){ Dt[P2[i]]=min(Dt[P2[i]],Dt[x]+E2[i]); if(E2[i]){ dq.push_back(P2[i]); }else dq.push_front(P2[i]); } } ;i<=n;i++) if(ds[i]!=inf)v[Ds[i]].push_back(i); ;num<cnt;num++){ int siz=v[num].size(); while(!pq.empty()&&Dt[pq.top().y]>=Ds[T]-num) pq.pop(); ;j<siz;j++){ x=v[num][j]; for(int i=H0[x];i;i=X0[i]){ if(Ds[P0[i]]>num&&cut[x]!=P0[i]) pq.push(A(x,P0[i],ds[x]+E0[i]+dt[P0[i]])); } } int xx,yy; if(!pq.empty()) xx=pq.top().x,yy=pq.top().y,ans[num]=pq.top().w; } ,x,y;i<Q;i++){ scanf("%d%d",&x,&y); if(cut[x]==y){ if(ans[Ds[x]]) printf("%lld\n",ans[Ds[x]]); else puts("Infinity"); }else if(cut[y]==x){ if(ans[Ds[y]]) printf("%lld\n",ans[Ds[y]]); else puts("Infinity"); }else{ printf("%lld\n",ds[T]); } } ed:; }