題意：在一個單位方格邊長為1的矩陣中藏著灰太狼和它的同伴，等待著喜羊羊和它的同伴，為了不讓喜羊羊和同伴被抓住，我們可以在矩形草坪中設置單位長度為1的柵欄，求最短的柵欄長度。

解題思路：這道題是要把狼和羊分開，如果熟悉最小割的話，就比較容易了，將所有的羊同源點連一條無窮大的邊，狼和匯點連一條無窮大的邊，剩下的格子與周圍格子連一條容量為1的邊，接下來就是求最小割即可。主要是為什么這樣建圖就是對的，首先是容量為1的邊，這個比較好理解，兩個相鄰格子只要加一個柵欄就可以隔開了。接下來是無窮大的邊，因為羊的限制是由它周圍的格子決定的，與源點無關，而且回顧最小割，羊與源點的邊集肯定不會在最小割集里，這樣也符合實際問題。

#include <cstring> #include <cstdlib> #include <cstring> #include <algorithm> #include <cstdio> #include <queue> #define INF 0x3fffffff #define MAXN 205 using namespace std;int N, M, G[MAXN][MAXN], dis[MAXN*MAXN]; int dir[2][2] = {0, 1, 1, 0}; int idx, head[MAXN*MAXN]; const int sink = MAXN*MAXN-1, source = MAXN*MAXN-2;struct Edge {int v, cap, next; }e[MAXN*MAXN*4];inline void init() { idx = -1;memset(head, 0xff, sizeof (head)); }inline int to(int x, int y) {return (x-1)*M+(y-1); }inline void insert(int a, int b, int c) {++idx;e[idx].v = b, e[idx].cap = c;e[idx].next = head[a], head[a] = idx; }inline bool judge(int x, int y) {if (x < 1 || x > N || y < 1 || y > M) {return false;}return true; }inline void check(int x, int y) {int xx, yy;if (G[x][y] == 1) {insert(to(x, y), sink, INF);insert(sink, to(x, y), 0); }else if (G[x][y] == 2) {insert(source, to(x, y), INF);insert(to(x, y), source, 0); } for (int i = 0; i < 2; ++i) {xx = x + dir[i][0], yy = y + dir[i][1];if (judge(xx, yy)) {insert(to(x, y), to(xx, yy), 1);insert(to(xx, yy), to(x, y), 1);}} }bool bfs() {int pos;queue<int>q;memset(dis, 0xff, sizeof (dis));dis[source] = 0;q.push(source);while (!q.empty()) {pos = q.front();q.pop();for (int i = head[pos]; i != -1; i = e[i].next) {if (dis[e[i].v] == -1 && e[i].cap > 0) {dis[e[i].v] = dis[pos]+1;q.push(e[i].v);}}}return dis[sink] != -1; }int dfs(int u, int flow) {if (u == sink) {return flow;}int tf = 0, sf;for (int i = head[u]; i != -1; i = e[i].next) {if (dis[u]+1 == dis[e[i].v] && e[i].cap > 0 && (sf = dfs(e[i].v, min(flow-tf, e[i].cap)))) {e[i].cap -= sf, e[i^1].cap += sf;tf += sf;if (tf == flow) {return flow;}}}if (!tf) {dis[u] = -1;}return tf; }int dinic() {int ans = 0;while (bfs()) {ans += dfs(source, INF);}return ans; }int main() { int ca = 0;while (scanf("%d %d", &N, &M) == 2) {init();for (int i = 1; i <= N; ++i) {for (int j = 1; j <= M; ++j) {scanf("%d", &G[i][j]);}}for (int i = 1; i <= N; ++i) {for (int j = 1; j <= M; ++j) {check(i, j);}}printf("Case %d:\n%d\n", ++ca, dinic());}return 0; }

總結

以上是生活随笔為你收集整理的hdu 3046(最小割最大流)的全部內容，希望文章能夠幫你解決所遇到的問題。

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