【题解】[ZJOI2009]狼和羊的故事

\(\text{Solution:}\)

显然思路，把所有羊看成一个源点，所有狼看成一个汇点，格子之间连容量为\(1\)的边，直接跑最小割。

技巧：

注意到篱笆不能把羊给割掉，狼同理。所以，我们可以建立一个超级源点\(S\)向所有羊连一条容量为\(inf\)的边。这样，在最小割中就一定不会把这条边割掉。对狼的处理同样。
对每个格子编号：想象成一张表格，对于点\((i,j)\)则前面已经经过了\(m(i-1)\)个格子，当前这个格子是第\(i\)行的第\(j\)个，于是它的编号应该是\((i-1)*m+j.\)不要写反！！！！！！

这题收获：注意到无限边在最小割中特殊的意义。

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MAXN=5e5+10;

const int inf=1e15;

int n,m,dep[MAXN],cur[MAXN],head[MAXN],tot=1,S,T;

struct edge{

	int nxt,to,flow;

}e[MAXN];

inline void add(int x,int y,int w){

	e[++tot].to=y;

	e[tot].nxt=head[x];

	head[x]=tot;e[tot].flow=w;

	e[++tot].to=x;

	e[tot].nxt=head[y];

	head[y]=tot;e[tot].flow=0;

}

bool bfs(int s,int t){

	memset(dep,0,sizeof(dep));

	queue<int>q;q.push(s);

	cur[s]=head[s];dep[s]=1;

	while(!q.empty()){

		s=q.front();q.pop();

		for(int i=head[s];i;i=e[i].nxt){

			int j=e[i].to;

			if(!dep[j]&&e[i].flow){

				dep[j]=dep[s]+1;

				cur[j]=head[j];

				if(j==t)return true;

				q.push(j);

			}

		}

	}

	return false;

}

int dfs(int s,int flow,int t){

	if(s==t||flow<=0)return flow;

	int rest=flow;

	for(int i=cur[s];i;i=e[i].nxt){

		int j=e[i].to;

		if(dep[j]==dep[s]+1&&e[i].flow){

			int tmp=dfs(j,min(rest,e[i].flow),t);

			if(tmp<=0)dep[j]=0;

			rest-=tmp;e[i].flow-=tmp;e[i^1].flow+=tmp;

			if(rest<=0)break;

		}

	}

	return flow-rest;

}

int dinic(int s,int t){

	int ans=0;

	for(;bfs(s,t);)ans+=dfs(s,inf,t);

	return ans;

}

inline int num(int x,int y){return (x-1)*m+y;}

signed main(){

	scanf("%lld%lld",&n,&m);

	S=0,T=num(n,m)+1;

	for(int i=1;i<=n;++i){

		for(int j=1;j<=m;++j){

			int pos=num(i,j);

			int x;scanf("%lld",&x);

			if(!x)continue;

			if(x==1)add(S,pos,inf);

			if(x==2)add(pos,T,inf);

		}

	}

	for(int i=1;i<=n;++i){

		for(int j=1;j<=m;++j){

			if(i-1>0)add(num(i,j),num(i-1,j),1);

			if(j-1>0)add(num(i,j),num(i,j-1),1);

			if(i+1<=n)add(num(i,j),num(i+1,j),1);

			if(j+1<=m)add(num(i,j),num(i,j+1),1);

		}

	}

	printf("%lld\n",dinic(S,T));

	return 0;

}

巴特西

【题解】[ZJOI2009]狼和羊的故事

最新文章

热门文章