LG2598/BZOJ1412 「ZJOI2009」狼和羊的故事最小割

问题描述

LG2598

BZOJ1412

题解

看到要把狼和羊两个物种分开

自然想到最小割。

发现\((x,y)\)可以向上下左右走以获得贡献，所以建边：\((x,y),(x-1,y)\),\((x,y),(x,y-1)\),\((x,y),(x,y+1)\),\((x,y),(x+1,y)\)（要在矩阵内）

这些边的边权为\(1\)，代表在这里建立栅栏（割断边）要\(1\)的代价

然后从源点向狼，羊向汇点建边，边权为\(INF\)，代表不可割断。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-'){

		fh=-1;ch=getchar();

	}

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

const int maxn=107;

const int INF=0x3f3f3f3f;

int n,m;

int a[maxn][maxn];

int S,T,d[maxn*maxn];

int Head[maxn*maxn],Next[1000007],v[1000007],tot=1,w[1000007];

int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

int Iter[maxn*maxn];

void add(int x,int y,int z){

	v[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;

}

int calc(int x,int y){//错误笔记：calc写错

	return (x-1)*m+y;

}

bool check(int x,int y){

	if(x>n||x<1||y>m||y<1) return false;

	return true;

}

int ans;

bool bfs(){

	memset(d,0,sizeof(d));

	queue<int>q;q.push(S);d[S]=1;

	while(!q.empty()){

		int x=q.front();q.pop();

		for(int i=Head[x];i;i=Next[i]){

			if(d[v[i]]||!w[i]) continue;

			q.push(v[i]);d[v[i]]=d[x]+1;

			if(v[i]==T) return true;

		}

	}

	return false;

}

int dfs(int x,int flow){

	if(x==T) return flow;

	int rest=flow;

	for(int i=Head[x];i&&rest;i=Next[i]){

		if(d[v[i]]!=d[x]+1||!w[i]) continue;

		int k=dfs(v[i],min(rest,w[i]));

		if(!k) d[v[i]]=0;

		else{

			w[i]-=k,w[i xor 1]+=k;

			rest-=k;

		}

	}

	return flow-rest;

}

int main(){

	read(n);read(m);

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

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

			read(a[i][j]);

		}

	}

	S=n*m+1,T=S+1;

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

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

			int p=calc(i,j);

			if(a[i][j]==1){

				add(S,p,INF);add(p,S,0);

			}

			else if(a[i][j]==2){

				add(p,T,INF);add(T,p,0);

			}

			for(int k=0;k<4;k++){

				int xx=i+dx[k],yy=j+dy[k];

				if(check(xx,yy)){

					add(p,calc(xx,yy),1),add(calc(xx,yy),p,0);

				}

			}

		}

	}

	while(bfs()){

		int t;

		for(int i=1;i<=n*m;i++) Iter[i]=Head[i];

		while(t=dfs(S,0x3f3f3f3f)) ans+=t;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

LG2598/BZOJ1412 「ZJOI2009」狼和羊的故事最小割

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

LG2598/BZOJ1412 「ZJOI2009」狼和羊的故事 最小割

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

LG2598/BZOJ1412 「ZJOI2009」狼和羊的故事最小割