2725: [Violet 6]故乡的梦
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 502 Solved: 173
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
6 7
1 2 1
2 3 1
3 4 2
4 5 1
5 6 1
1 3 3
4 6 3
1 6
4
1 2
1 3
4 3
6 5
1 2 1
2 3 1
3 4 2
4 5 1
5 6 1
1 3 3
4 6 3
1 6
4
1 2
1 3
4 3
6 5
Sample Output
7
6
Infinity
7
6
Infinity
7
HINT
Source
Solution
一道非常强的图论题
网上很多做法是直接求出最短路，然后直接用线段树维护，这种做法有反例(这句话划掉吧..都是从策爷博客看来的
首先我们考虑，如果ST不连通，那显然全部输出Infinity
我们先做两遍Dijsktra，求出S出发到所有点的单源最短路ds[]，以及T出发到所有点的单源最短路dt[]
那么我们发现，如果删除的边不存在最短路径上，那么显然答案全都是ds[T]
考虑利用ds[]和dt[]的信息，构建一种新的图 最短路径图Gs 即满足ds[u]+val(u-->v)=ds[v]的边所构成的图，同理做出Gt
那么我们需要找到GsGt中的割边，因为只有割这种边，才会使得最短路径发生变化
那么问题在于如何求，Tarjan的方法，正确性位置，不妨考虑最小割，
所以我们假定每条边容量为1，我们在Gs上进行增广，如果MinCut>=2，那么任意删一条边对结果不造成影响，因为只需要知道是否>=2所以增广两次即可
那么当最小割为1时，我们需要求割边，这时候利用Tarjan，
在残余网络上跑tarjan求出所有SCC，记belong[u]为点u所在SCC的编号。显然有belong[s]!=belong[t]（否则s到t有通路，能继续增广）。
①对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当belong[u]!=belong[v]；
②对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当belong[u]==belong[s]且belong[v]==belong[t]。 应用:BZOJ1797
求出这些割边后，我们知道，删除非割边并不影响答案，所以输出ds[T]，只有割边会对答案有影响
同样的，Gs中的割边反向就是Gt中的割边
那么我们求出这些割边，cut(1~K)，显然我们可以离线的处理出每条割边的答案，然后O（1）询问
我们对最短路径图Gs再进行改动，其中的割边我们设val=1，非割边val=0，然后我们可以求出Gs，Gt中S/T到每个点的最短路（0/1）构成
这个实现起来可以利用 BFS+双端队列
然后我们可以离线的处理出每个cut的答案，这个过程可以利用multiset/heap/线段树 来实现
堆的方法：
维护一个小根堆，关键字是ds[u]+val(u-->v)+dt[v]，具体的方法就是 当前计算的是now，先将之前的状态（Dt[v]>=Sum-now)弹出，然后把当前的所有出边加入到堆中，然后用堆顶答案去更新接下来的值
线段树的方法：
区间覆盖取最小的经典模型，先修改，再DFS一遍整棵线段树即可
multiset的方法：
扫描cut的时候，记录所有可行的答案，然后取最小来更新即可
总的时间复杂度是$O((N+M)+NlogN)$
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
void Freopen() {freopen("dream.in","r",stdin); freopen("dream.out","w",stdout);}
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define LL long long
#define MAXN 200010
#define MAXM 200010
int N,M,Q;
struct EdgeNode{int next,to,val;}edge[MAXM<<];
int head[MAXN],cnt=;
void AddEdge(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].val=w;}
void InsertEdge(int u,int v,int w) {AddEdge(u,v,w); AddEdge(v,u,w);} #define Pa pair<LL,int>
priority_queue<Pa,vector<Pa>,greater<Pa> >q;
#define INF (1LL<<50)
LL ds[MAXN],dt[MAXN];
int S,T;
void Dijsktra(int ss,int tt,LL dis[MAXN])
{
for (int i=; i<=N; i++) dis[i]=INF;
q.push(make_pair(,ss)); dis[ss]=;
while (!q.empty())
{
int now=q.top().second;
long long Dis=q.top().first;
q.pop();
if (Dis>dis[now]) continue;
for (int i=head[now]; i; i=edge[i].next)
if (dis[now]+edge[i].val<dis[edge[i].to])
dis[edge[i].to]=dis[now]+edge[i].val,
q.push(make_pair(dis[edge[i].to],edge[i].to));
}
}
//=================================================================
struct SideNode{int next,to,val,from;}side[MAXM];
int first[MAXN],num=;
void AddSide(int u,int v,int w) {num++; side[num].from=u; side[num].next=first[u]; first[u]=num; side[num].to=v; side[num].val=w;} struct RoadNode{int next,to,cap,from,val;}road[MAXM<<];
int last[MAXN],tot=;
void AddRoad(int u,int v,int w) {tot++; road[tot].next=last[u]; last[u]=tot; road[tot].cap=w; road[tot].to=v; road[tot].from=u;}
void InsertRoad(int u,int v,int w) {AddRoad(u,v,w); AddRoad(v,u,);}
void BuildGraph()
{
for (int i=; i<=N; i++)
for (int j=head[i]; j; j=edge[j].next)
{
if (ds[i]+edge[j].val==ds[edge[j].to])
InsertRoad(i,edge[j].to,);
if (dt[edge[j].to]==dt[i]+edge[j].val)
AddSide(i,edge[j].to,);
}
}
int h[MAXN];
bool bfs()
{
queue<int>que;
for (int i=; i<=N; i++) h[i]=-;
que.push(S); h[S]=;
while (!que.empty())
{
int now=que.front(); que.pop();
for (int i=last[now]; i; i=road[i].next)
if (road[i].cap && h[road[i].to]==-)
h[road[i].to]=h[now]+,que.push(road[i].to);
}
return h[T]!=-;
}
int dfs(int now,int low)
{
if (now==T) return low;
int w,used=;
for (int i=last[now]; i; i=road[i].next)
if (road[i].cap && h[road[i].to]==h[now]+)
{
w=dfs(road[i].to,min(low-used,road[i].cap));
used+=w;
road[i].cap-=w; road[i^].cap+=w;
if (used==low) return low;
}
if (!used) h[now]=-;
return used;
}
int dinic()
{
int tim=,tmp=;
while (bfs() && tim--) {tmp+=dfs(S,);}
return tmp;
}
//=================================================================
int dfn[MAXN],low[MAXN],DFN,stack[MAXN],top,scc,size[MAXN],belong[MAXN];
bool visit[MAXN];
void Tarjan(int now)
{
low[now]=dfn[now]=++DFN; visit[now]=;
stack[++top]=now;
for (int i=last[now]; i; i=road[i].next)
{
if (road[i].cap==) continue;
if (!dfn[road[i].to])
Tarjan(road[i].to),low[now]=min(low[now],low[road[i].to]);
else
if (visit[road[i].to]) low[now]=min(low[now],dfn[road[i].to]);
}
int tp=;
if (dfn[now]==low[now])
{
scc++;
while (now!=tp)
tp=stack[top--],size[scc]++,visit[tp]=,belong[tp]=scc;
}
}
void Tarjan() {for (int i=; i<=N; i++) {if (!dfn[i]) Tarjan(i);}}
//=================================================================
LL Ds[MAXN],Dt[MAXN];
bool mark[MAXN];
void BFS1()
{
deque<int>dq;
for (int i=; i<=N; i++) Ds[i]=INF,mark[i]=;
dq.push_back(S); Ds[S]=;
while (!dq.empty())
{
int now=dq.front(); dq.pop_front();
if (mark[now]) continue; else mark[now]=;
for (int i=last[now]; i; i=road[i].next)
if (!(i&))
{
Ds[road[i].to]=min(Ds[now]+road[i].val,Ds[road[i].to]);
if (road[i].val) dq.push_back(road[i].to); else dq.push_front(road[i].to);
}
}
}
void BFS2()
{
for (int i=; i<=N; i++) Dt[i]=INF,mark[i]=;
dq.push_back(T); Dt[T]=;
while (!dq.empty())
{
int now=dq.front(); dq.pop_front();
if (mark[now]) continue; else mark[now]=;
for (int i=first[now]; i; i=side[i].next)
{
Dt[side[i].to]=min(Dt[now]+side[i].val,Dt[side[i].to]);
if (side[i].val) dq.push_back(side[i].to); else dq.push_front(side[i].to);
}
}
}
//=================================================================
struct Node
{
int u,v; LL val;
Node(int u=,int v=,LL val=)
: u(u),v(v),val(val) {}
bool operator < (const Node & A) const
{return val>A.val;}
};
priority_queue<Node>heap;
vector<int>vec[MAXN];
int cut[MAXN];
LL ans[MAXN];
void Solve()
{
for (int i=; i<=N; i++) if (ds[i]!=INF) vec[Ds[i]].push_back(i);
for (int i=; i<scc; i++)
{
int sz=vec[i].size();
while (!heap.empty() && Dt[heap.top().v]>=Ds[T]-i) heap.pop();
for (int j=; j<=sz-; j++)
{
int now=vec[i][j];
for (int k=head[now]; k; k=edge[k].next)
if (Ds[edge[k].to]>i && cut[now]!=edge[k].to)
heap.push( Node(now,edge[k].to,ds[now]+edge[k].val+dt[edge[k].to]) );
}
if (!heap.empty()) ans[i]=heap.top().val;
}
}
int main()
{
N=read(),M=read();
for (int x,y,z,i=; i<=M; i++)
x=read(),y=read(),z=read(),InsertEdge(x,y,z);
S=read(),T=read();
Dijsktra(S,T,ds); Dijsktra(T,S,dt);
if (ds[T]==INF) {Q=read(); while (Q--) puts("Infinity"); return ;}
BuildGraph();
if (dinic()>=) {Q=read(); while (Q--) printf("%lld\n",ds[T]); return ;}
Q=read();
Tarjan();
for (int i=; i<=tot; i+=)
if (!road[i].cap && belong[road[i].from]!=belong[road[i].to])
cut[road[i].from]=road[i].to,road[i].val=;
for (int i=; i<=num; i++)
if (cut[side[i].to]==side[i].from) side[i].val=;
BFS1(); BFS2();
Solve();
for (int i=; i<=Q; i++)
{
int x=read(),y=read();
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 if (cut[x]!=y && cut[y]!=x) printf("%lld\n",ds[T]);
}
return ;
}