來自FallDream的博客，未經(jīng)允許，請(qǐng)勿轉(zhuǎn)載，謝謝qaq

---

A,B兩個(gè)國家正在交戰(zhàn)，其中A國的物資運(yùn)輸網(wǎng)中有N個(gè)中轉(zhuǎn)站，M條單向道路。設(shè)其中第i (1≤i≤M)條道路連接了vi,ui兩個(gè)中轉(zhuǎn)站，那么中轉(zhuǎn)站vi可以通過該道路到達(dá)ui中轉(zhuǎn)站，如果切斷這條道路，需要代價(jià)ci。現(xiàn)在B國想找出一個(gè)路徑切斷方案，使中轉(zhuǎn)站s不能到達(dá)中轉(zhuǎn)站t，并且切斷路徑的代價(jià)之和最小。? 小可可一眼就看出，這是一個(gè)求最小割的問題。但愛思考的小可可并不局限于此。現(xiàn)在他對(duì)每條單向道路提出兩個(gè)問題：?? 問題一：是否存在一個(gè)最小代價(jià)路徑切斷方案，其中該道路被切斷？? 問題二：是否對(duì)任何一個(gè)最小代價(jià)路徑切斷方案，都有該道路被切斷？?? 現(xiàn)在請(qǐng)你回答這兩個(gè)問題。

n<=4000 m<=60000

題解：先跑一次最小割，然后在殘量網(wǎng)絡(luò)上tarjan，用所有沒滿流的邊縮點(diǎn)。

由于是最小割，所以顯然ST不在同一塊

一條邊如果沒有滿流，那么它就不可能被割了。在這基礎(chǔ)上：

　　一條邊可以被割當(dāng)且僅當(dāng)連接的兩個(gè)點(diǎn)所屬的塊不同。

　　一條邊一定被割當(dāng)且僅當(dāng)連接的兩個(gè)點(diǎn)分別和S,T同塊。

證明我不會(huì)，轉(zhuǎn)一個(gè)鏼爺(jcvb)的題解：

<==將每個(gè)SCC縮成一個(gè)點(diǎn)，得到的新圖就只含有滿流邊了。那么新圖的任一s-t割都對(duì)應(yīng)原圖的某個(gè)最小割，從中任取一個(gè)把id[u]和id[v]割開的割即可證明。

?< ==：假設(shè)將(u,v)的邊權(quán)增大，那么殘余網(wǎng)絡(luò)中會(huì)出現(xiàn)s->u->v->t的通路，從而能繼續(xù)增廣，于是最大流流量（也就是最小割容量）會(huì)增大。這即說明(u,v)是最小割集中必須出現(xiàn)的邊。

#include<iostream> #include<cstdio> #include<cstring> #define ll long long #define MN 4000 #define INF 2000000000 using namespace std; inline int read() {int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }int n,m,S,T,head[MN+5],cnt=1,d[MN+5],c[MN+5],q[MN+5],top,dn=0,dfn[MN+5],low[MN+5],bel[MN+5],cc=0; struct edge{int from,to,next,w;}e[120005];inline void ins(int f,int t,int w) {e[++cnt]=(edge){f,t,head[f],w};head[f]=cnt;e[++cnt]=(edge){t,f,head[t],0};head[t]=cnt; }int dfs(int x,int f) {if(x==T)return f;int used=0;for(int&i=c[x];i;i=e[i].next)if(e[i].w&&d[e[i].to]==d[x]+1){int w=dfs(e[i].to,min(f-used,e[i].w));used+=w;e[i].w-=w;e[i^1].w+=w;if(used==f)return used;}return d[x]=-1,used; }bool bfs() {memset(d,0,sizeof(d));int i,j;for(d[q[top=i=1]=S]=1;i<=top;i++)for(j=c[q[i]]=head[q[i]];j;j=e[j].next)if(e[j].w&&!d[e[j].to])d[q[++top]=e[j].to]=d[q[i]]+1;return d[T]; }void tarjan(int x) {dfn[x]=low[x]=++dn;q[++top]=x;for(int i=head[x];i;i=e[i].next)if(e[i].w){if(!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);elseif(!bel[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); }if(dfn[x]==low[x])for(++cc;q[top+1]!=x;--top)bel[q[top]]=cc; }int main() {n=read();m=read();S=read();T=read();for(int i=1;i<=m;i++){int u=read(),v=read(),c=read();ins(u,v,c);}while(bfs()) dfs(S,INF); top=0;memset(q,0,sizeof(q));for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);for(int i=2;i<=cnt;i+=2)printf("%d %d\n",!e[i].w&&bel[e[i].from]!=bel[e[i].to],bel[e[i].from]==bel[S]&&bel[e[i].to]==bel[T]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/FallDream/p/bzoj1797.html

總結(jié)

以上是生活随笔為你收集整理的[bzoj1797][Ahoi2009]Mincut 最小割的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。