首页 > 代码库 > ZJOI2009 狼和羊的故事
ZJOI2009 狼和羊的故事
既然这题这么水,我就不写了……
挖掘栅栏的本质:只能建在相邻两个,且建好后使得狼和羊之间不存在通路。而割的定义是:使S集和T集不存在通路。而题目又要求建的栅栏最少,于是就是最小割问题了。
从源点向所有狼连一条∞的边,从所有羊向汇点连一条∞的边,这样就能保证狼和羊都在不同的点集里。然后再从狼到相邻的羊和空地,空地到相邻的空地和羊连一条流量为1的边,最大流求最小割即可。
或者将所有点向四周连边。。就是时间长了点 --hzwer
代码:(来自hzwer)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define inf 0x7fffffff 5 #define T 10001 6 using namespace std; 7 int head[10005],q[10005],h[10005]; 8 int cnt=1,ans,n,m; 9 int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0},mp[105][105];10 struct data{int to,next,v;}e[500001];11 void ins(int u,int v,int w)12 {e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}13 void insert(int u,int v,int w)14 {ins(u,v,w);ins(v,u,0);}15 bool bfs()16 {17 int t=0,w=1,i,now;18 memset(h,-1,sizeof(h));19 q[0]=0;h[0]=0;20 while(t<w)21 {22 now=q[t];t++;i=head[now];23 while(i)24 {25 if(e[i].v&&h[e[i].to]==-1)26 {27 h[e[i].to]=h[now]+1;28 q[w++]=e[i].to;29 }30 i=e[i].next;31 }32 }33 return h[T]==-1? 0:1;34 }35 int dfs(int x,int f)36 {37 if(x==T)return f;38 int w,used=0,i;39 i=head[x];40 while(i)41 {42 if(e[i].v&&h[e[i].to]==h[x]+1)43 {44 w=f-used;45 w=dfs(e[i].to,min(w,e[i].v));46 e[i].v-=w;47 e[i^1].v+=w;48 used+=w;49 if(used==f)return f;50 }51 i=e[i].next;52 }53 if(!used)h[x]=-1;54 return used;55 }56 void dinic(){while(bfs())ans+=dfs(0,inf);}57 void ini()58 {59 scanf("%d%d",&n,&m);60 for(int i=1;i<=n;i++)61 for(int j=1;j<=m;j++)62 scanf("%d",&mp[i][j]);63 }64 void build()65 {66 for(int i=1;i<=n;i++)67 for(int j=1;j<=m;j++)68 {69 if(mp[i][j]==1)insert(0,(i-1)*m+j,inf);70 else if(mp[i][j]==2)insert((i-1)*m+j,T,inf);71 for(int k=0;k<4;k++)72 {73 int nowx=i+xx[k],nowy=j+yy[k];74 if(nowx<1||nowx>n||nowy<1||nowy>m||mp[i][j]==2)continue;75 if(mp[i][j]!=1||mp[nowx][nowy]!=1)76 insert((i-1)*m+j,(nowx-1)*m+nowy,1);77 }78 }79 }80 int main()81 {82 ini();83 build();84 dinic();85 printf("%d",ans);86 return 0;87 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。