http://acm.hdu.edu.cn/showproblem.php?pid=3046
题意：
给出矩阵地图和羊和狼的位置，求至少需要建多少栅栏，使得狼不能到达羊。
思路：
狼和羊不能到达，最小割最大流问题。
因为狼和羊都有多只，所以我们加一个超级源点和一个超级汇点，将每只狼与超级源点相连，容量为INF，将每只羊与超级汇点相连，容量为INF。对于地图上的点，每个点都与它上下左右相连，容量设为1。
接下来，我们只需要计算出从超级源点到超级汇点的最大流，因为最小割等于最大流。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
using namespace std; const int maxn = *;
const int INF = 0x3f3f3f3f; struct Edge
{
int from,to, cap, flow;
Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){}
}; int n, m,t;
vector<Edge> edges;
vector<int> G[maxn];
int vis[maxn];
int d[maxn]; //从起点到i的距离
int cur[maxn]; //当前弧下标
int flow; void init()
{
for (int i = ; i < maxn; i++)
G[i].clear();
edges.clear();
} void AddEdge(int from, int to, int cap)
{
edges.push_back(Edge(from, to, cap, ));
edges.push_back(Edge(to, from, , ));
int m = edges.size();
G[from].push_back(m - );
G[to].push_back(m - );
} int BFS()
{
memset(vis, , sizeof(vis));
queue<int> Q;
Q.push();
d[] = ;
vis[] = ;
while (!Q.empty())
{
int x = Q.front();
Q.pop();
for (int i = ; i < G[x].size(); i++)
{
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap>e.flow)
{
vis[e.to] = ;
d[e.to] = d[x] + ;
Q.push(e.to);
}
}
}
return vis[n*m + ];
} int DFS(int x,int a)
{
if (x == n*m + || a == ) return a;
int flow = , f;
for (int& i = cur[x]; i < G[x].size(); i++)
{
Edge& e = edges[G[x][i]];
if (d[x] + == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow)))>)
{
e.flow += f;
edges[G[x][i] ^ ].flow -= f;
flow += f;
a -= f;
if (a == ) break;
}
}
return flow;
} void Maxflow(int s,int t)
{
flow = ;
while (BFS())
{
memset(cur, , sizeof(cur));
flow += DFS(s, INF);
}
} int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int kase = ;
int a;
while (~scanf("%d%d", &n, &m))
{
init();
for (int i = ; i <= n;i++)
for (int j = ; j <= m; j++)
{
if (i != )
AddEdge((i - )*m + j, (i-)*m+j, );
if (i != n)
AddEdge((i - )*m + j, i*m + j, );
if (j != )
AddEdge((i - )*m + j, (i - )*m + j - , );
if (j != m)
AddEdge((i - )*m + j, (i - )*m + j + , );
scanf("%d", &a);
if (a == )
AddEdge(, (i - )*m + j, INF);
else if (a == )
AddEdge((i - )*m + j, m*n + , INF);
}
Maxflow(, n*m + );
printf("Case %d:\n%d\n", ++kase, flow);
}
}