Maxflow

第一行两个正整数n（1≤n≤100,000）和m（1≤m≤n+100）表示图的点数和边数。
接下来m行每行两个正整数a和b（1≤a,b≤n）表示图中的m条边。保证是连通简单图。
接下来一行一个正整数Q（1≤Q≤100,000）表示询问的组数。
接下来Q行每行两个不同的正整数x和y（1≤x,y≤n）表示一组询问。

1
2
3
4
5
6
7
8
import java.util.Scanner;
public class Main {
    public static void main(String[] arg) {
        Scanner scanner = new Scanner(System.in);
        // todo
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<cstdio>

#include<vector>

const int maxn=100010,maxm=210000,maxv=210;

struct Edge{int to,cap;Edge*rev,*next;};

struct Graph{

int n;

Edge E[maxm],*ne,*fir[maxn];

void init(int n){ne=E;for(int i=this->n=n;i>=0;i--)fir[i]=0;}

void link(int a,int b,int c=1){

*ne=(Edge){b,c,ne+1,fir[a]};fir[a]=ne++;

*ne=(Edge){a,c,ne-1,fir[b]};fir[b]=ne++;

}

}G1,G2,T;

int dfn[maxn],low[maxn],now,stk[maxn],top,bcc[maxn];

void cmin(int&a,int b){b<a?a=b:1;}

void dfs1(int i,int f){

dfn[i]=low[i]=++now;

stk[top++]=i;

for(Edge*e=G1.fir[i];e;e=e->next){

if(!dfn[e->to]){

dfs1(e->to,i);

cmin(low[i],low[e->to]);

}

else if(e->to!=f)cmin(low[i],dfn[e->to]);

}

if(low[i]==dfn[i]){

do bcc[stk[--top]]=i;

while(stk[top]!=i);

}

int id[maxn],tot;

void dfs2(int s,int i,int f){

if(id[i])id[s]<id[i]?G2.link(id[s],id[i]),1:1;

else for(Edge*e=G1.fir[i];e;e=e->next)if(bcc[e->to]==bcc[i]&&e->to!=f)dfs2(s,e->to,i);

}

Edge*cur[maxv];

int Q[maxv],D[maxv];

int dfs(int i,int t,int c){

if(i==t||!c)return c;

int fl=0,f;

for(Edge*&e=cur[i];e&&c;e=e->next)

if(e->cap&&D[e->to]==D[i]-1&&(f=dfs(e->to,t,c<e->cap?c:e->cap)))

fl+=f,e->cap-=f,e->rev->cap+=f,c-=f;

return fl;

}

int mf(int s,int t){

for(int f=0;;f+=dfs(s,t,1<<30)){

for(int i=0;i<=G2.n;i++)D[i]=0,cur[i]=G2.fir[i];

for(int*H=Q,*T=Q+(D[*Q=t]=1);H<T;H++)

for(Edge*e=G2.fir[*H];e;e=e->next)

if(e->rev->cap&&!D[e->to])D[*T++=e->to]=D[*H]+1;

if(!D[s])return f;

}

void solve(std::vector<int>V){

if(V.size()<2)return;

for(Edge*e=G2.E;e<G2.ne;e++)e->cap=1;

T.link(V[0],V[1],mf(V[0],V[1]));

std::vector<int>V0,V1;

for(int i=0;i<V.size();i++)D[V[i]]?V1.push_back(V[i]):V0.push_back(V[i]);

solve(V0);

solve(V1);

}

int f[maxv][maxv];

void dfs_t(int s,int i,int fa,int v){

f[s][i]=v;

for(Edge*e=T.fir[i];e;e=e->next)

if(e->to!=fa)dfs_t(s,e->to,i,v<e->cap?v:e->cap);

}

int main(){

int n,m;

scanf("%d%d",&n,&m);

G1.init(n);

for(int i=0;i<m;i++){

int a,b;

scanf("%d%d",&a,&b);

G1.link(a,b);

}

dfs1(1,0);

std::vector<int>V;

for(int i=1;i<=n;i++){

int d=0;

for(Edge*e=G1.fir[i];e;e=e->next)if(bcc[e->to]==bcc[i])d++;

if(d>2)V.push_back(id[i]=++tot);

}

G2.init(tot);

T.init(tot);

for(int i=1;i<=n;i++)if(id[i])

for(Edge*e=G1.fir[i];e;e=e->next)if(bcc[e->to]==bcc[i])dfs2(i,e->to,i);

solve(V);

for(int i=1;i<=tot;i++)dfs_t(i,i,i,1<<30);

int Q;

scanf("%d",&Q);

while(Q--){

int x,y;

scanf("%d%d",&x,&y);

printf("%d\n",bcc[x]!=bcc[y]?1:id[x]&&id[y]?f[id[x]][id[y]]:2);

}

详情