首页 > 代码库 > UVa1515 Pool construction (最小割)
UVa1515 Pool construction (最小割)
链接：http://vjudge.net/problem/UVA-1515
分析：首先分析一个特例，如果草地“#”和洞“.”不允许相互转化，那么我们可以直接从草地‘#”出发向图中相邻洞格子“.”连一条容量为b的弧，源点S向所有草地“#”连一条弧，所有洞“.”向汇点T连一条弧，容量均为无穷大，那么最小割就是建围栏的总费用。
这道题在上述基础上加了草地和洞可以相互转化这一条件。根据刚才的思路，我们可以联想到，只要草地“#”转化成洞“.”的时候，就不需要在它和周围的洞“.”之间建围栏了，那么我们可以限制源点s到草地“#”的容量为d，表示把这条弧切断，这个草格子就成为了洞跑到了T阵营和周围的洞成为一个连通块。同样，限制洞“.”到汇点的容量为f。注意：和特例中不同的是，这次相邻两个格子u和v之间需要连两条边u->v和v->u，容量均为b，原因是每个草格子都有可能变成洞，这时就需要和原本同属于一个连通块的草格子之间建围栏，洞格子亦然。
1 #include <cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<vector> 5 #include<algorithm> 6 using namespace std; 7 8 const int maxn = 2500 + 5; 9 const int INF = 1000000000; 10 11 struct Edge { 12 int from, to, cap, flow; 13 Edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f) {} 14 }; 15 16 struct EdmondsKarp { 17 int n, m; 18 vector<Edge> edges; 19 vector<int> G[maxn]; 20 int a[maxn]; 21 int p[maxn]; 22 23 void init(int n) { 24 for (int i = 0; i < n; i++) G[i].clear(); 25 edges.clear(); 26 } 27 28 void AddEdge(int from, int to, int cap) { 29 edges.push_back(Edge(from, to, cap, 0)); 30 edges.push_back(Edge(to, from, 0, 0)); 31 m = edges.size(); 32 G[from].push_back(m - 2); 33 G[to].push_back(m - 1); 34 } 35 36 int Maxflow(int s, int t) { 37 int flow = 0; 38 for (;;) { 39 memset(a, 0, sizeof(a)); 40 queue<int> Q; 41 Q.push(s); 42 a[s] = INF; 43 while (!Q.empty()) { 44 int x = Q.front(); Q.pop(); 45 for (int i = 0; i < G[x].size(); i++) { 46 Edge& e = edges[G[x][i]]; 47 if (!a[e.to] && e.cap > e.flow) { 48 p[e.to] = G[x][i]; 49 a[e.to] = min(a[x], e.cap - e.flow); 50 Q.push(e.to); 51 } 52 } 53 if (a[t]) break; 54 } 55 if (!a[t]) break; 56 for (int u = t; u != s; u = edges[p[u]].from) { 57 edges[p[u]].flow += a[t]; 58 edges[p[u] ^ 1].flow -= a[t]; 59 } 60 flow += a[t]; 61 } 62 return flow; 63 } 64 }; 65 66 EdmondsKarp g; 67 int w, h, d, f, b; 68 char mp[55][55]; 69 70 inline int ID(int i, int j) { return i * w + j; } 71 72 int main() { 73 int T; 74 scanf("%d", &T); 75 while (T--) { 76 scanf("%d%d%d%d%d", &w, &h, &d, &f, &b); 77 int cost = 0; 78 for (int i = 0; i < h; i++) { 79 getchar(); 80 for (int j = 0; j < w; j++) { 81 scanf("%c", &mp[i][j]); 82 if (i == 0 || i == h - 1 || j == 0 || j == w - 1) 83 if (mp[i][j] == ‘.‘) { mp[i][j] = ‘#‘; cost += f; } 84 } 85 } 86 g.init(w * h + 2); 87 for (int i = 0; i < h; i++) 88 for (int j = 0; j < w; j++) { 89 if (mp[i][j] == ‘#‘) { 90 int cap = d; 91 if (i == 0 || i == h - 1 || j == 0 || j == w - 1) cap = INF; 92 g.AddEdge(w * h, ID(i, j), cap); 93 } else g.AddEdge(ID(i, j), w * h + 1, f); 94 if (i - 1 >= 0) g.AddEdge(ID(i, j), ID(i - 1, j), b); 95 if (i + 1 < h) g.AddEdge(ID(i, j), ID(i + 1, j), b); 96 if (j - 1 >= 0) g.AddEdge(ID(i, j), ID(i, j - 1), b); 97 if (j + 1 < w) g.AddEdge(ID(i, j), ID(i, j + 1), b); 98 } 99 printf("%d\n", cost + g.Maxflow(w * h, w * h + 1));100 }101 return 0;102 }
UVa1515 Pool construction (最小割)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。