挺簡(jiǎn)單一個(gè)題，最小割模板

我的感覺就是可能建圖的時(shí)候會(huì)比較麻煩吧，畢竟三個(gè)方向。

#include <cctype> #include <climits> #include <cstdio> #include <cstring> #include <iostream>#define debug(x) std::cout << #x << " = " << x << std::endl;#define __OPTIMIZED__INPUT__ int nextInt() {int num = 0;char c;bool flag = false;while ((c = std::getchar()) == ' ' || c == '\r' || c == '\n' || c == '\t');if (c == '-')flag = true;elsenum = c - 48;while (std::isdigit(c = std::getchar()))num = num * 10 + c - 48;return (flag ? - 1 : 1) * num; }struct {int to;int nex;int v; } e[600001]; int head[600001]; int h[600001], q[600001]; int ans, n, m;void Insert(const int u, const int v, const int w) {static int tot = 0;tot++;e[tot].to = v;e[tot].v = w;e[tot].nex = head[u];head[u] = tot; }bool bfs() {int now, i;std::memset(h, 0xff, sizeof h);int t = 0;int w = 1;q[t] = 1;h[1] = 0;while (t < w){now = q[t];t++;i = head[now];for (int i = head[now]; i; i = e[i].nex)if (e[i].v && h[e[i].to] < 0){q[w++] = e[i].to;h[e[i].to] = h[now] + 1;}}if (h[n * m] == -1)return 0;return 1; }int dfs(const int x, const int f) {if (x == n * m)return f;int w, used = 0;for (int i = head[x]; i; i = e[i].nex)if (e[i].v && h[e[i].to] == h[x] + 1){w = dfs(e[i].to, std::min(w, e[i].v));e[i].v -= w;e[i + 1].v += w;used += w;if (used == f)return f;}if (!used)h[x] = -1; // debug(used);return used; }void Dinic() {while (bfs())ans += dfs(1, INT_MAX); }int main(int argc, char ** argv) {n = nextInt();m = nextInt();int x;for (int i = 1; i <= n; i++)for (int j = 1; j < m; j++){x = nextInt();Insert(m * (i - 1) + j, m * (i - 1) + j + 1, x);Insert(m * (i - 1) + j + 1, m * (i - 1) + j, x);}for (int i = 1; i < n; i++)for (int j = 1; j <= m; j++){x = nextInt();Insert(m * (i - 1) + j, m * i + j, x);Insert(m * i + j, m * (i - 1) + j, x);}for (int i = 1; i < n; i++)for (int j = 1; j < m; j++){x = nextInt();Insert(m * (i - 1) + j, m * i + j + 1, x);Insert(m * i + j + 1, m * (i - 1) + j, x);}Dinic();std::cout << ans/* << std::endl*/; #ifdef __NOTEPADPPstd::cin.get();std::cin.get(); #endifreturn 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/edwardtsui/p/6782858.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ1001】[BeiJing2006]狼抓兔子的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。