題面

題目傳送門

解法

把\(S\)集看作和羊連接，\(T\)看作和狼連接

然后就轉化成了基本的最小割模型了

對于0的處理，可以把它放在羊和狼兩排點的中間，由\(S\rightarrow\)羊\(\rightarrow0\rightarrow\)狼\(\rightarrow T\)

然后跑dinic即可

代碼

#include <bits/stdc++.h> #define inf 1 << 30 #define N 110 using namespace std; template <typename node> void chkmax(node &x, node y) {x = max(x, y);} template <typename node> void chkmin(node &x, node y) {x = min(x, y);} template <typename node> void read(node &x) {x = 0; int f = 1; char c = getchar();while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f; } struct Edge {int next, num, c; } e[N * N * N]; int dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1}; int n, m, s, t, cnt, a[N][N], l[N * N], cur[N * N]; void add(int x, int y, int c) {e[++cnt] = (Edge) {e[x].next, y, c};e[x].next = cnt; } void Add(int x, int y, int c) {add(x, y, c), add(y, x, 0); } int calc(int x, int y) {return (x - 1) * m + y; } bool bfs(int s) {for (int i = 1; i <= t; i++) l[i] = -1;queue <int> q; q.push(s);while (!q.empty()) {int x = q.front(); q.pop();for (int p = e[x].next; p; p = e[p].next) {int k = e[p].num, c = e[p].c;if (c && l[k] == -1)l[k] = l[x] + 1, q.push(k);}}return l[t] != -1; } int dfs(int x, int lim) {if (x == t) return lim;int used = 0;for (int p = cur[x]; p; p = e[p].next) {int k = e[p].num, c = e[p].c;if (c && l[k] == l[x] + 1) {int w = dfs(k, min(c, lim - used));e[p].c -= w, e[p ^ 1].c += w; used += w;if (e[p].c) cur[x] = p;if (used == lim) return lim;}}if (!used) l[x] = -1;return used; } int dinic() {int ret = 0;while (bfs(s)) {for (int i = 0; i <= t; i++)cur[i] = e[i].next;ret += dfs(s, inf);}return ret; } int main() {read(n), read(m);for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)read(a[i][j]);s = 0, t = cnt = n * m + 1;if (cnt % 2 == 0) cnt++;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {int x = calc(i, j);if (a[i][j] == 1) Add(s, x, inf);if (a[i][j] == 2) {Add(x, t, inf); continue;}for (int k = 1; k <= 4; k++) {int tx = i + dx[k], ty = j + dy[k];if (!tx || !ty || tx > n || ty > m) continue;int y = calc(tx, ty);if (a[tx][ty] == 2) Add(x, y, 1);else if (!a[tx][ty]) Add(x, y, 1);}}cout << dinic() << "\n";return 0; }

轉載于:https://www.cnblogs.com/copperoxide/p/9476782.html

總結

以上是生活随笔為你收集整理的bzoj 1412 [ZJOI2009]狼和羊的故事 最小割建图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。