最大流最小割定理介绍：把一个流网络的顶点集划分成两个集合S和T，使得源点s ∈S且汇点t ∈T，割(S,T)的容量C(S,T) = ∑ Cuv, 其中u∈S且v∈T。
从直观上看，截集(S,T)是从源点s到汇点t的必经之路，如果该路堵塞则流从s无法到达t。于是我们可以得到
最大流最小割定理：任意一个流网络的最大流量等于该网络的最小的割的容量。
最小割问题：
ZOJ@2788 题意：在一栋楼中有若干房间，一个房间有若干扇门通往别的房间，现在房间中有一个secure room。由于有一些敌人已经潜入某一些房间，现在问关闭最少的一些门，使得敌人们到达不了secure room。对于一扇门连通A-B，若控制面板CP在A方，则总是可以从A->B，但是若关上门，则B不能到达A。
解法：最大流。首先通过floyd算法判断是否敌人总是可以到达secure room，如果能直接输出结果；如果不能，则通过最大流算法求解即可。对于一扇门A-B，CP在A方则从A连一条有向边到B，容量为无穷大，从B连一条边到A，容量为1。两个房间之间可能有多扇门，边的容量累加即可。增加一个源点，从源点连边到有敌人的房间，容量为1。对图求最大流即为结果。
代码如下：
// 2389732 2011-01-20 15:06:16 Accepted 2788 C++ 0 184 *******
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 22
#define inf 1000000
int map[MAXN][MAXN];
int flow[MAXN][MAXN];
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
int pre[MAXN],que[MAXN],p,q,t,i,j;
int d[MAXN];
int tmp;
if (source==sink) return inf;
for (i=0;i<n;i++)
for (j=0;j<n;flow[i][j++]=0);
for (;;){
for (i=0;i<n;pre[i++]=0);
pre[t=source]=source+1,d[t]=inf;
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
for (i=0;i<n;i++)
if (!pre[i]&&(tmp=mat[t][i]-flow[t][i]))
pre[que[q++]=i]=t+1,d[i]=d[t]<tmp?d[t]:tmp;
else if (!pre[i]&&(tmp=flow[i][t]))
pre[que[q++]=i]=-t-1,d[i]=d[t]<tmp?d[t]:tmp;
if (!pre[sink]) break;
for (i=sink;i!=source;)
if (pre[i]>0)
flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
else
flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
}
tmp = 0;
for (i=0;i<n;tmp+=flow[source][i++]);
return tmp;
}
int main()
{
int T, n, m, k, y;
char str[3];
int d[MAXN];
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
n++;
memset(map,0,sizeof(map));
memset(flow,0,sizeof(flow));
for(int i = 1; i <= m; i++){
scanf("%s %d",str, &k);
d[i] = (strlen(str) == 1);
if(d[i])map[0][i] = inf;
for(int j = 0; j < k; j++){
scanf("%d",&y);
y++;
flow[i][y] = 1;
map[i][y] += inf;
map[y][i] += 1;
}
}
// Checking always exists a path to secure room. Output "PANIC ROOM BREACH"!
for(k = 1; k <= m; k++)
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++)
if(flow[i][k]&&flow[k][j])
flow[i][j] = 1;
for(k = 1; k <= m && !(d[k] && flow[k][n]); k++);
if(k <= m)
printf("PANIC ROOM BREACH\n");
else
printf("%d\n", max_flow(m+1,map,0,n,flow));
}
return 0;
}