今天邱神给我们讲了图论，还讲了一下网络流算法。自己找了一个洛谷板子题。
题目描述 农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由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; else return 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 */