题目大意：在一个n*m的矩阵上，1代表羊，2代表狼，0代表平地，我们有长度为1的一个栅栏（不是放在格子上的，是放在格子和格子之间的空隙上的），问使用最少的栅栏，能够使得狼吃不到羊。
又学到了一招，以前一直以为建图是要先设好S点T点，在把其他的点和他们两一一相连。今天学到了原来可以在整个map上根据条件建好图，再把其中的某些目标点和源汇点相连的。
思路如下：
1、建立最小割模型：
①建立源点S，将源点S连入各个有狼的节点上，权值设定为INF，表示狼可以从任意方向出发。 ②建立汇点T，将各个羊节点连入汇点T，权值设定为INF。 ③将每两个相邻的格子之间建立一条边，权值设定为1，表示如果拆掉了这条边，这条边就不能走了
#include#include #include #include #define MAX 400000#define INF 0x1f1f1f1fusing namespace std;int map[210][210];int ss, tt;int n, m;int cont;int head[MAX];int d[4][2] = { {0,1},{0,-1},{-1,0},{1,0} };int divv[MAX];int cur[MAX];struct edge { int from, to, w, next;}e[MAX];void add(int u, int v, int w) { e[cont].from = u; e[cont].to = v; e[cont].w = w; e[cont].next = head[u]; head[u] = cont++;}int makediv() { memset(divv, 0, sizeof(divv)); divv[ss] = 1; queue Q; Q.push(ss); while (!Q.empty()) { int u = Q.front(); if (u == tt) return 1; Q.pop(); for (int i = head[u]; i != -1; i = e[i].next) { int w = e[i].w; int v = e[i].to; if (divv[v] == 0 && w) { divv[v] = divv[u] + 1; Q.push(v); } } } return 0;}int DFS(int u, int maxflow, int tt) { if (u == tt) return maxflow; int ret = 0; for (int &i = cur[u]; i != -1; i = e[i].next) { int v = e[i].to; int w = e[i].w; if (divv[v] == divv[u] + 1 && w) { int f = DFS(v, min(maxflow - ret, w), tt); e[i].w -= f; e[i ^ 1].w += f; ret += f; if (ret == maxflow) return ret; } } return ret;}int kase = 0;void Dinic() { int ans = 0; while (makediv() == 1) { memcpy(cur, head, sizeof(head)); ans += DFS(ss, INF, tt); } printf("Case %d:\n%d\n", ++kase, ans);}int main(void) { kase = 0; while (~scanf("%d%d", &n, &m)) { memset(head, -1, sizeof(head)); cont = 0; ss = 0; tt = n * m + 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &map[i][j]); if (map[i][j] == 2) { //每只狼都可以从任意方向出发 add(ss, (i - 1)*m + j, INF); add((i - 1)*m + j, ss, 0); } if (map[i][j] == 1) { add((i - 1)*m + j, tt, INF); add(tt, (i - 1)*m + j, 0); } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int t = 0; t < 4; t++) { int xx = i + d[t][0]; int yy = j + d[t][1]; if (xx > 0 && xx <= n && yy > 0 && yy <= m) { add((i - 1)*m + j, (xx - 1)*m + yy, 1); add((xx - 1)*m + yy, (i - 1)*m + j, 0); } } } } Dinic(); } return 0;}