ZJOI2009狼和羊的故事

题目描述

“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。通过仔细观察，Orez发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。

输入输出格式

输入格式：

文件的第一行包含两个整数n和m。接下来n行每行m个整数，1表示该格子属于狼的领地，2表示属于羊的领地，0表示该格子不是任何一只动物的领地。

输出格式：

文件中仅包含一个整数ans，代表篱笆的最短长度。

输入样例#1:

2 2 2 2 1 1

输出样例#1:

解析：

狼和羊被分开等于说任意狼和羊不连通，容易想到最小割。把狼和羊(1和2)分成两部分，源点向1连边，2向汇点连边，容量inf；1和2交界处连边，然后0向四周连边(因为0周围可任意切割)，1向相邻的2连边，容量为1。然后Dinic或者ISAP。

以下是我的代码(依然比较宽。。)：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #define S (n * m + 1)
  5 #define T (n * m + 2)
  6 #define ID(x, y) ((x) * m + (y))
  7 #define INF 0x7f7f7f7f
  8 using namespace std;
  9 
 10 const int dx[] = {0, 0, 1, -1};
 11 const int dy[] = {-1, 1, 0, 0};
 12 
 13 struct Edge
 14 {
 15 	int v, next, cap;
 16 	Edge(int a = 0, int b = 0, int c = 0)
 17 	:v(a), next(b), cap(c){};
 18 }edge[100020];
 19 int n, m, cnt;
 20 int head[10010], cur[10010], dep[10010], map[10010];
 21 
 22 void AddEdge(int _u, int _v, int _c)
 23 {
 24 	edge[cnt] = Edge(_v, head[_u], _c);
 25 	head[_u] = cnt++;
 26 	edge[cnt] = Edge(_u, head[_v], 0);
 27 	head[_v] = cnt++;
 28 }
 29 bool bfs()
 30 {
 31 	int queue[10010], qHead = 0, qTail = 0;
 32 	queue[qTail++] = S;
 33 	memset(dep, 0, sizeof(dep));
 34 	dep[S] = 1;
 35 	while(qTail > qHead)
 36 	{
 37 		int p = queue[qHead++];
 38 		for(int i = head[p]; ~i; i = edge[i].next)
 39 			if(edge[i].cap && !dep[edge[i].v])
 40 			{
 41 				dep[edge[i].v] = dep[p] + 1;
 42 				queue[qTail++] = edge[i].v;
 43 			}
 44 	}
 45 	return dep[T];
 46 }
 47 bool dfs(int now)
 48 {
 49 	if(now == T) return true;
 50 	for(int &i = cur[now]; ~i; i = edge[i].next)
 51 		if(edge[i].cap && dep[edge[i].v] == dep[now] + 1 && dfs(edge[i].v))
 52 		{
 53 			edge[i].cap--, edge[i ^ 1].cap++;
 54 			return true;
 55 		}
 56 	return false;
 57 }
 58 int Dinic()
 59 {
 60 	int res = 0;
 61 	while(bfs())
 62 	{
 63 		memcpy(cur, head, sizeof(head));
 64 		while(dfs(S))
 65 			res++;
 66 	}
 67 	return res;
 68 }
 69 int main()
 70 {
 71 	memset(head, -1, sizeof(head));
 72 	scanf("%d%d", &n, &m);
 73 	for(int i = 0; i < n; i++)
 74 		for(int j = 0; j < m; j++)
 75 			scanf("%d", &map[ID(i, j)]);
 76 	for(int i = 0; i < n; i++)
 77 		for(int j = 0; j < m; j++)
 78 			switch(map[ID(i, j)])
 79 			{
 80 				case 1:
 81 					AddEdge(S, ID(i, j), INF);
 82 					for(int k = 0; k < 4; k++)
 83 						if(i + dx[k] < n && i + dx[k] >= 0
 84 						&& j + dy[k] < m && j + dy[k] >= 0
 85 						&& map[ID(i + dx[k], j + dy[k])] != 1)
 86 							AddEdge(ID(i, j), ID(i + dx[k], j + dy[k]), 1);
 87 					break;
 88 				case 2:
 89 					AddEdge(ID(i, j), T, INF);
 90 					for(int k = 0; k < 4; k++)
 91 						if(i + dx[k] < n && i + dx[k] >= 0
 92 						&& j + dy[k] < m && j + dy[k] >= 0
 93 						&& map[ID(i + dx[k], j + dy[k])] == 0)
 94 							AddEdge(ID(i + dx[k], j + dy[k]), ID(i, j), 1);
 95 					break;
 96 				default:
 97 					for(int k = 0; k < 4; k++)
 98 						if(i + dx[k] < n && i + dx[k] >= 0
 99 						&& j + dy[k] < m && j + dy[k] >= 0
100 						&& map[ID(i + dx[k], j + dy[k])] == 0)
101 							AddEdge(ID(i, j), ID(i + dx[k], j + dy[k]), 1);
102 			}
103 	printf("%d
", Dinic());
104 
105 	return 0;
106 }//Rhein_E

View Code