最小割板子题——[USACO5.4]奶牛的电信

今天邱神给我们讲了图论，还讲了一下网络流算法。自己找了一个洛谷板子题。

题目描述农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由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]奶牛的电信的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。