本文主要是介绍HDU 3046Pleasant sheep and big big wolf（网络流之最小割），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：HDU 3046
最小割第一发！其实也没什么发不发的。。。最小割==最大流。。
入门题，但是第一次入手最小割连入门题都完全没思路。。。sad。。对最小割的本质还是了解的不太清楚。。
这题就是对每两个相邻的格子的边界都要进行加边，然后求最大流就OK了。
RE了好长时间，注意遍历加边的时候要从1开始，而不是0开始，因为0是源点的。。。（也许只有我才犯这种错误吧。。。）建图不多说了。。只要了解了最小割，建图还是很容易想的。
代码如下：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int head[100000], source, sink, nv, cnt;
int cur[100000], num[100000], d[100000], pre[100000], q[100000], mp[300][300];
struct node
{int u, v, cap, next;
} edge[10000000];
void add(int u, int v, int cap)
{edge[cnt].v=v;edge[cnt].cap=cap;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].v=u;edge[cnt].cap=0;edge[cnt].next=head[v];head[v]=cnt++;
}
void bfs()
{memset(d,-1,sizeof(d));memset(num,0,sizeof(num));int f1=0, f2=0, i;d[sink]=0;num[0]=1;q[f1++]=sink;while(f1>=f2){int u=q[f2++];for(i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(d[v]==-1){d[v]=d[u]+1;num[d[v]]++;q[f1++]=v;}}}
}
void isap()
{memcpy(cur,head,sizeof(cur));bfs();int flow=0, u=pre[source]=source, i;while(d[source]<nv){if(u==sink){int f=INF,pos;for(i=source;i!=sink;i=edge[cur[i]].v){if(f>edge[cur[i]].cap){f=edge[cur[i]].cap;pos=i;}}for(i=source;i!=sink;i=edge[cur[i]].v){edge[cur[i]].cap-=f;edge[cur[i]^1].cap+=f;}flow+=f;u=pos;}for(i=cur[u];i!=-1;i=edge[i].next){if(d[edge[i].v]+1==d[u]&&edge[i].cap)break;}if(i!=-1){cur[u]=i;pre[edge[i].v]=u;u=edge[i].v;}else{if(--num[d[u]]==0) break;int mind=nv;for(i=head[u];i!=-1;i=edge[i].next){if(mind>d[edge[i].v]&&edge[i].cap){mind=d[edge[i].v];cur[u]=i;}}d[u]=mind+1;num[d[u]]++;u=pre[u];}}printf("%d\n",flow);
}
int main()
{int n, m, i, j, num=0;while(scanf("%d%d",&n,&m)!=EOF){num++;memset(head,-1,sizeof(head));cnt=0;source=0;sink=n*m+1;nv=sink+1;for(i=1; i<=n; i++){for(j=1; j<=m; j++){scanf("%d",&mp[i][j]);if(i!=1)add((i-1)*m+j,(i-2)*m+j,1);if(i!=n)add((i-1)*m+j,i*m+j,1);if(j!=1)add((i-1)*m+j,(i-1)*m+j-1,1);if(j!=m)add((i-1)*m+j,(i-1)*m+j+1,1);if(mp[i][j]==1)add(source,(i-1)*m+j,INF);else if(mp[i][j]==2)add((i-1)*m+j,sink,INF);}}printf("Case %d:\n",num);isap();}return 0;
}
这篇关于HDU 3046Pleasant sheep and big big wolf（网络流之最小割）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
