$ POJ~1966~Cable~TV~Network $

---

---

$ solution: $

第一眼可能讓人很難下手，但本就是沖著網(wǎng)絡流來的，所以我們直接一點。這道題我們要讓這個聯(lián)通圖斷開，那么勢必會有兩個點變得不連通，這道題的數(shù)據(jù)范圍很小，所以我們試著暴力枚舉兩個點。這樣就變成了最小割。不過，嗯？割的東西怎么是點？

為了靠近我們已經(jīng)學得知識，我們想辦法看，能不能割點變成割邊。反正網(wǎng)絡流最喜歡千變萬化、左右建模了。。。于是我們引進書上的一個東西：

一個節(jié)點可以拆成兩個節(jié)點，將原節(jié)點用中間那條邊表示

一條邊可以拆成兩條邊，將原邊用中間那個點表示

中間的邊權為1代表這個點是否被割，旁邊的邊權為inf是為了排除其影響（因為它不可能被割掉）

我們用第一條和第三條性質可以解決這個問題。首先對于每個節(jié)點建立兩個 $ i $ 和 $ i+n $ 節(jié)點。然后這兩個節(jié)點之間用一條權值為1的有向邊（從 $ i $ 到 $ i+n $ ） ，如果這條邊在最小割中被割掉（等價于原本的點被割掉）。然后 $ i $ 節(jié)點連入邊（權值正無窮）， $ i+n $ 節(jié)點連出邊（權值正無窮），連正無窮是為了讓割掉的邊只能是中間的邊。然后我們跑一遍最大流，它對應的最小割里每條代表原來一個點，因為權值為1，所以流量就是答案。

注意：我們的源匯點也要被分為兩個點，而網(wǎng)絡流中的實際源點是 $ S+n $ ，它連出邊。因為源匯點的性質，這兩個點不可能被割掉，所以它們中間不連邊。

---

---

$ code: $

#include<iostream> #include<cstdio> #include<iomanip> #include<algorithm> #include<cstring> #include<cstdlib> #include<ctime> #include<cmath> #include<vector> #include<queue> #include<map> #include<set>#define ll long long #define db double #define rg register intusing namespace std;int n,m,S,T; int ans,top=1; int dep[505]; int tou[505]; int qi[505]; int f[55][55];struct su{int to,v,next; }b[5005];inline int qr(){register char ch; register bool sign=0; rg res=0;while(!isdigit(ch=getchar()))if(ch=='-')sign=1;while(isdigit(ch))res=res*10+(ch^48),ch=getchar();if(sign)return -res; else return res; }inline void add(int x,int y,int v){ //注意博主加邊自帶反向b[++top]=su{y,v,tou[x]}; tou[x]=top;b[++top]=su{x,0,tou[y]}; tou[y]=top; }inline bool bfs(int x){for(rg i=1;i<=x;++i)qi[i]=tou[i],dep[i]=0;queue<int> q; q.push(S); dep[S]=1;while(!q.empty()){rg i=q.front(); q.pop();for(rg j=tou[i];j;j=b[j].next)if(b[j].v&&!dep[b[j].to]){dep[b[j].to]=dep[i]+1;if(b[j].to==T)return 1;q.push(b[j].to);}} return 0; }inline int dfs(int i,int w){if(i==T||!w)return w;rg rest=w,f;for(rg &j=qi[i];j;j=b[j].next){if(b[j].v&&dep[b[j].to]==dep[i]+1){f=dfs(b[j].to,min(w,b[j].v));if(!f){dep[b[j].to]=-2; continue;}b[j].v-=f; b[j^1].v+=f; w-=f;} if(!w)break;}return rest-w; }inline void solve(){rg res=0; top=1;for(rg i=1;i<=n*2+2;++i) tou[i]=0; //初始化for(rg i=1;i<=n;++i){if(i!=S&&i!=T)add(i,i+n,1); //一點拆成兩點，中間連邊f(xié)or(rg j=1;j<=n;++j)if(f[i][j])add(i+n,j,1e9); //連邊注意是否有加n操作} S=S+n;while(bfs(n*2+2)) res+=dfs(S,1e9); //DInicans=min(res,ans); }int main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);rg t=qr();while(t--){n=qr();m=qr();for(rg i=1;i<=n;++i){for(rg j=i;j<=n;++j){f[i][j]=f[j][i]=0; //初始化}}for(rg i=1;i<=m;++i){rg x=qr()+1,y=qr()+1;f[x][y]=f[y][x]=1; //鄰接矩陣讀邊}if(n==0||n==2){puts("0");continue;}if(m==0&&n&&n!=2){puts("1");continue;}//特判，這題有點卡細節(jié)ans=1e9;for(rg i=1;i<=n;++i){for(rg j=1;j<=n;++j){if(f[i][j]||i==j)continue; //注意兩個相鄰的點不可能通過割點不聯(lián)通S=i;T=j; solve(); //枚舉源匯點}} if(ans==1e9)ans=n; //無論怎么割點圖都聯(lián)通，就輸出nprintf("%d\n",ans);}return 0; }

轉載于:https://www.cnblogs.com/812-xiao-wen/p/11257791.html

總結

以上是生活随笔為你收集整理的POJ 1966 Cable TV Network （最大流最小割）的全部內容，希望文章能夠幫你解決所遇到的問題。

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