[原博客] BZOJ 2725 : [Violet 6]故乡的梦

这个题在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:;
 }