正題

題目鏈接:https://www.luogu.com.cn/problem/P4126

---

題目大意

給出$n$個點$m$條邊的一張有向圖和起點終點。對于每條邊求其是否是最小割的可行割/必須割

$1\le n\le 4000,1\le m\le 60000$

---

解題思路

一些結論吧，首先是可行割，跑一次最大流，然后如果一條邊是可行割需要滿足

• 該邊滿流
• 殘量網絡上沒有$x,y$之間的環

首先滿流是顯然的，然后第二個結論的話，如果它們之間有環，那么從$y$順著環的方向逆流回去的話那么最大流不變但是這條邊的流量減少了。

然后必須割的話也是兩個條件

• 該邊滿流
• 殘量網絡上$s$能到$x$，$y$能到$t$

這個我直接搬之前的證明了

證明:在殘量網絡上$s$可以到達$x$且$y$可以到達$t$那么說明若該邊不割那么$s$就可以通過該邊到達$t$。假設在$s$到$x$的路上有同樣長度的一條道路且割掉后可以使$s$到達$x$那么在殘量網絡上該邊的流量必定為0，因為切割掉$x?>y$的流量也必定會經過該邊所以在殘量網絡上$s$就不可以到達$x$了。所以該假設不成立。
證畢

所以跑完最大流再跑一次$tarjan$然后按照上面判就好了

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<queue> using namespace std; const int N=4100,M=6e4+10,inf=1e9; struct node{int to,next,w; }a[M<<1]; int n,m,s,t,tot,cnt,num,ls[N],id[M]; int dep[N],dfn[N],low[N],col[N]; bool ins[N]; stack<int> st;queue<int> q; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;return; } bool bfs(){while(!q.empty())q.pop();q.push(s);memset(dep,0,sizeof(dep));dep[s]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[y]||!a[i].w)continue;dep[y]=dep[x]+1;if(y==t)return 1;q.push(y);}}return 0; } int dinic(int x,int flow){if(x==t)return flow;int rest=0,k;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[x]+1!=dep[y]||!a[i].w)continue;rest+=(k=dinic(y,min(flow-rest,a[i].w)));a[i].w-=k;a[i^1].w+=k;if(rest==flow)return rest;}if(!rest)dep[x]=0;return rest; } void tarjan(int x){dfn[x]=low[x]=++cnt;ins[x]=1;st.push(x);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!a[i].w)continue;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(ins[y])low[x]=min(low[x],dfn[y]);}if(low[x]==dfn[x]){int k;++num;do{k=st.top();st.pop();col[k]=num;ins[k]=0;}while(k!=x);}return; } signed main() {scanf("%d%d%d%d",&n,&m,&s,&t);tot=1;for(int i=1;i<=m;i++){int x,y,w;id[i]=tot+1;scanf("%d%d%d",&x,&y,&w);addl(x,y,w);}while(bfs())dinic(s,inf);for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=m;i++){int x=a[id[i]^1].to,y=a[id[i]].to;if(a[id[i]].w==0&&col[x]!=col[y])putchar('1');else putchar('0');putchar(' ');if(a[id[i]].w==0&&col[x]==col[s]&&col[y]==col[t])putchar('1');else putchar('0');putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的P4126-[AHOI2009]最小割【网络流,tarjan】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。