最大流最小割定理介紹：把一個流網(wǎng)絡的頂點集劃分成兩個集合S和T，使得源點s ∈S且匯點t ∈T，割(S,T)的容量C(S,T) = ∑ Cuv, 其中u∈S且v∈T。
從直觀上看，截集(S,T)是從源點s到匯點t的必經(jīng)之路，如果該路堵塞則流從s無法到達t。于是我們可以得到
最大流最小割定理：任意一個流網(wǎng)絡的最大流量等于該網(wǎng)絡的最小的割的容量。
最小割問題：
ZOJ@2788 題意：在一棟樓中有若干房間，一個房間有若干扇門通往別的房間，現(xiàn)在房間中有一個secure room。由于有一些敵人已經(jīng)潛入某一些房間，現(xiàn)在問關閉最少的一些門，使得敵人們到達不了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;
}