世界快资讯丨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:

2

解析：

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

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

1 #include2 #include3 #include4 #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] >= 0100 && 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\n", Dinic());104 105 return 0;106 }//Rhein_E

View Code 返回顶部 收缩

转载于:https://www.cnblogs.com/Rhein-E/p/9323589.html