今天邱神給我們講了圖論，還講了一下網絡流算法。自己找了一個洛谷板子題。

題目描述農夫約翰的奶牛們喜歡通過電郵保持聯系，于是她們建立了一個奶牛電腦網絡，以便互相交流。這些機器用如下的方式發送電郵：如果存在一個由c臺電腦組成的序列a1,a2,...,a(c)，且a1與a2相連，a2與a3相連，等等，那么電腦a1和a(c)就可以互發電郵。很不幸，有時候奶牛會不小心踩到電腦上，農夫約翰的車也可能碾過電腦，這臺倒霉的電腦就會壞掉。這意味著這臺電腦不能再發送電郵了，于是與這臺電腦相關的連接也就不可用了。有兩頭奶牛就想：如果我們兩個不能互發電郵，至少需要壞掉多少臺電腦呢？請編寫一個程序為她們計算這個最小值。以如下網絡為例：1* / 3 - 2*這張圖畫的是有2條連接的3臺電腦。我們想要在電腦1和2之間傳送信息。電腦1與3、2與3直接連通。如果電腦3壞了，電腦1與2便不能互發信息了。 輸入輸出格式 輸入格式：第一行 四個由空格分隔的整數：N,M,c1,c2.N是電腦總數(1<=N<=100)，電腦由1到N編號。M是電腦之間連接的總數(1<=M<=600)。最后的兩個整數c1和c2是上述兩頭奶牛使用的電腦編號。連接沒有重復且均為雙向的(即如果c1與c2相連，那么c2與c1也相連)。兩臺電腦之間至多有一條連接。電腦c1和c2不會直接相連。第2到M+1行 接下來的M行中，每行包含兩臺直接相連的電腦的編號。輸出格式：一個整數表示使電腦c1和c2不能互相通信需要壞掉的電腦數目的最小值。輸入輸出樣例 輸入樣例#1： 復制3 2 1 2 1 3 2 3輸出樣例#1： 復制1

?

?之前說最小割的答案等于最大流，但是發現直接寫是不對的。為什么呢？因為這個題有一個坑！就是這個題其實不是求的是最小割邊，而是最小割點。最小割邊的答案就是最大流的答案，但是最小割點不是啊。。。怎么辦呢？

只能轉化。把割點再構圖的時候轉化成割邊就行了唄！怎么構圖呢？我們考慮拆點，把一個點拆為兩個，之間的連邊為1，然后題上給的邊的權值設為無限大。然后跑最大流就可以了！

上代碼：

#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define inf 99999999 template <class T> void read(T &x) {char c;bool op = 0;while(c = getchar(),c > '9' || c < '0')if(c == '-') op = 1;x = c - '0';while(c = getchar(),c >= '0' && c <= '9')x = x * 10 + c - '0';if(op == 1)x = -x; } struct node{int x,y,c,nxt,other; }; node a[21110000]; int len = 0,last[5000],st,ed; int list[5000]; void add(int x,int y,int w) {int k1,k2;a[++len].nxt = last[x];k1 = len;a[len].x = x;a[len].y = y;a[len].c = w;last[x] = len;a[++len].nxt = last[y];k2 = len;a[len].x = y;a[len].y = x;a[len].c = 0;last[y] = len;a[k1].other = k2;a[k2].other = k1; } int h[5001]; bool bfs() {memset(h,0,sizeof(h));h[st] = 1;int head,tail;list[1] = st;head = 1;tail = 2;while(head != tail){int x = list[head];for(int k = last[x];k;k = a[k].nxt){int y = a[k].y;if(a[k].c > 0 && h[y] == 0){h[y] = h[x] + 1;list[tail++] = y;}}head++;}if(h[ed] > 0)return true;elsereturn false; } int find(int x,int f) {if(x == ed){return f;}int s = 0,t;for(int k = last[x];k;k = a[k].nxt){int y = a[k].y;if(s < f && h[y] == (h[x] + 1) && a[k].c > 0){t = find(y,min(a[k].c,f - s));s += t;a[k].c -= t;a[a[k].other].c += t;}}if(s == 0)h[x] = 0;return s; } int main() {int n,m;read(n);read(m);read(st);read(ed);len = 0;st += n;memset(last,0,sizeof(last));duke(i,1,n){add(i,i + n,1);add(i + n,i,0);}duke(i,1,m){int x,y,z;read(x);read(y);add(x + n,y,inf);add(x,y + n,0);add(y + n,x,inf);add(y,x + n,0);}int s = 0,t;int l = 0;while(bfs() == true){s += find(st,inf);}cout<<s<<endl;return 0; } /* 3 2 1 2 1 3 2 3 */

?

轉載于:https://www.cnblogs.com/DukeLv/p/9416431.html

總結

以上是生活随笔為你收集整理的最小割板子题——[USACO5.4]奶牛的电信的全部內容，希望文章能夠幫你解決所遇到的問題。

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