我勒個擦，我們OJ竟然還有我沒做的網(wǎng)絡流的題目，昨天在dsh的推薦下，今天試著寫了一下，題目，由于事先已經(jīng)知道是最小割了，所以建模沒有什么太大的難度了。
解法：朋友之間連邊，從源點到相信African swallow可以carry coconuts的人連邊，否則從這個人到匯點連邊，容量都為1，主義朋友之間連雙向邊，求最大流(最小割)即為結(jié)果。
#include <stdio.h>
#include <string.h>
#define N 305
#define INF 1 << 29
int g[N][N], cnt[N], dis[N], pre[N];
void Pre()
{
memset(g, 0, sizeof(g));
}
int ISAP(int src, int sink, int n)
{
int maxflow = 0, flow, u = src, v, d;
memset(cnt, 0, sizeof(cnt));
memset(dis, 0, sizeof(dis));
pre[src] = src;
cnt[0] = n;
while(dis[src] < n)
{
if(u == sink)
{
flow = INF;
for(int i = sink; i != src; i = pre[i])
if(g[pre[i]][i] < flow)
{
flow = g[pre[i]][i];
}
maxflow += flow;
u = src;
for(int i = sink; i != src; i = pre[i])
{
g[pre[i]][i] -= flow;
g[i][pre[i]] += flow;
}
}
for(d = n, v = 0; v < n; v++)
{
if(!g[u][v]) continue;
d = d < dis[v] ? d : dis[v];
if(dis[v] + 1 == dis[u]) break;
}
if(v < n) pre[v] = u, u = v;
else
{
if(!(--cnt[dis[u]])) break;
++cnt[dis[u] = d + 1];
u = pre[u];
}
}
return maxflow;
}
int main()
{
int n, m, src, sink, a, b, c;
while(scanf("%d %d", &n, &m), n + m)
{
Pre();
src = 0, sink = n + 1;
for(int i = 1; i <= n; i++)
{
scanf("%d", &c);
if(c) g[src][i] = 1;
else g[i][sink] = 1;
}
for(int i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
g[a][b] = g[b][a] = 1;
}
int ans = ISAP(src, sink, n + 2);
printf("%d\n", ans);
}
return 0;
}