題意：

給定n*m個(gè)點(diǎn)的矩陣

0為空點(diǎn)。1為羊。2為狼

相鄰點(diǎn)之間有一條路。

問要使得狼與羊不連通最少要去掉幾條邊

最小割

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<queue> #include<vector> using namespace std;#define ll int #define N 40010 #define M 105000 #define inf 1073741824 #define inf64 1152921504606846976 struct Edge{ ll from, to, cap, nex, max; }edge[M*4];//注意這個(gè)一定要夠大 不然會(huì)re 還有反向弧 ll head[N], edgenum; void add(ll u, ll v, ll cap){ Edge E = { u, v, cap, head[u],cap}; edge[ edgenum ] = E; head[u] = edgenum ++; Edge E2= { v, u, 0, head[v],cap}; edge[ edgenum ] = E2; head[v] = edgenum ++; } ll sign[N]; bool BFS(ll from, ll to){ memset(sign, -1, sizeof(sign)); sign[from] = 0; queue<ll>q; q.push(from); while( !q.empty() ){ int u = q.front(); q.pop(); for(ll i = head[u]; i!=-1; i = edge[i].nex) { ll v = edge[i].to; if(sign[v]==-1 && edge[i].cap) { sign[v] = sign[u] + 1, q.push(v); if(sign[to] != -1)return true; } } } return false; } ll Stack[N], top, cur[N]; ll dinic(ll from, ll to){ ll ans = 0; while( BFS(from, to) ) { memcpy(cur, head, sizeof(head)); ll u = from; top = 0; while(1) { if(u == to) { ll flow = inf, loc;//loc 表示 Stack 中 cap 最小的邊 for(ll i = 0; i < top; i++) if(flow > edge[ Stack[i] ].cap) { flow = edge[Stack[i]].cap; loc = i; } for(ll i = 0; i < top; i++) { edge[ Stack[i] ].cap -= flow; edge[Stack[i]^1].cap += flow; } ans += flow; top = loc; u = edge[Stack[top]].from; } for(ll i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增廣的邊的下標(biāo) if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break; if(cur[u] != -1) { Stack[top++] = cur[u]; u = edge[ cur[u] ].to; } else { if( top == 0 )break; sign[u] = -1; u = edge[ Stack[--top] ].from; } } } return ans; } void init(){memset(head,-1,sizeof head);edgenum = 0;}int mp[205][205]; int n, m; int Hash(int x,int y){return (x-1)*m+y;} bool inmap(int x,int y){return 1<=x&&x<=n&&1<=y&&y<=m;} int w[N], s[N], step[4][2] = {1,0,-1,0,0,1,0,-1}; int main() {int u, v, d, i, j, Cas = 1;while(~scanf("%d %d",&n,&m)){init();int wt = 0, st = 0;for(i = 1; i <= n; i++){for(j = 1; j <= m; j++){scanf("%d",&mp[i][j]);int now = Hash(i,j);if(mp[i][j]==1)s[st++] = now;if(mp[i][j]==2)w[wt++] = now;for(int k = 0; k < 4; k++){if(!inmap(i+step[k][0], j+step[k][1]))continue;int go = Hash(i+step[k][0], j+step[k][1]);add(now, go, 1);}}}int from = 0, to = Hash(n,m)+1;for(i = 0; i < wt; i++)add(from, w[i], inf);for(i = 0; i < st; i++)add(s[i], to, inf);printf("Case %d:\n%d\n",Cas++,dinic(from, to));}return 0; } /* 4 6 1 0 0 1 0 0 0 1 1 0 0 0 2 0 0 0 0 0 0 2 0 1 1 0*/

總結(jié)

以上是生活随笔為你收集整理的HDU 3046 Pleasant sheep and big big wolf 最小割的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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