[ZJOI2009]狼和羊的故事

题面

描述

洛谷 P2598

狼爱上羊啊爱的疯狂,谁让他们真爱了一场;

狼爱上羊啊并不荒唐,他们说有爱就有方向……

Orez 听到这首歌,心想:狼和羊如此和谐,为什么不尝试羊狼合养呢?说干就干! Orez 的羊狼圈可以看作一个 n*m 个矩阵格子,这个矩阵的边缘已经装上了篱笆。可是 Drake 很快发现狼再怎么也是狼,它们总是对羊垂涎三尺,那首歌只不过是一个动人的传说而已。所以 Orez 决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。 通过仔细观察,Orez 发现狼和羊都有属于自己领地,若狼和羊们不能呆在自己的领地,那它们就会变得非常暴躁,不利于他们的成长。 Orez 想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地,再就是篱笆必须修筑完整,也就是说必须修建在单位格子的边界上并且不能只修建一部分。

输入格式

文件的第一行包含两个整数 n 和 m。接下来 n 行每行 m 个整数,1 表示该格子属于狼的领地,2 表示属于羊的领地,0 表示该格子不是任何一只动物的领地。

输出格式

文件中仅包含一个整数 ans,代表篱笆的最短长度。

思路

考虑建网格图($(x,y)$ 到 $(x-1,y)$,$(x+1,y)$,$(x,y-1)$,$(x,y+1)$ 建边),要让狼到羊之间无法到达,就是在求一个最小割。

$S$ 到每只狼(或羊)连边,每只狼(或羊)到 $T$ 连边,权值为 $+ \infty$,跑一遍最大流(最大流 = 最小割)。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,last[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005],d[200005];
void add(int a,int b,int c){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    last[a]=top;
}
bool bfs(long long S,long long T){
    memset(v,0,sizeof(v));
    memset(d,63,sizeof(d));
    queue<long long> q;
    q.push(S);
    v[S]=1;
    d[S]=0;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        v[now]=0;
        for (int i=last[now];i;i=nextt[i]){
            int j=to[i];
            if (d[j]>d[now]&&s[i]){
            	d[j]=d[now]+1;
            	if (!v[j]){
	            	q.push(j);
	            	v[j]=1;
				}
			}
        }
    }
    if (d[T]<1000000000){
    	return 1;
	}
    return 0;
}
int dfs(long long x,long long minn,long long T){
	if (x==T){
		return minn;
	}
	int now=minn,tmp=0;
	for (int i=last[x];i&&now;i=nextt[i]){
        int j=to[i];
        if (d[j]==d[x]+1&&s[i]){
			tmp=dfs(j,min(minn,s[i]),T);
			if (tmp){
	            s[i]-=tmp;
	            s[i^1]+=tmp;
	            now-=tmp;
			}
		}
    }
    return minn-now;
}
long long dinic(long long S,long long T){
	long long ans=0,tmp=0;
	while (bfs(S,T)){
		while (1){
			tmp=dfs(S,2147483647,T);
			if (!tmp){
				break;
			}
			ans+=tmp;
		}
	}
    return ans;
}
inline int calc(int x,int y){
	return (x-1)*m+y;
}
int main(){
    long long S=40005,T=40006;
    int a[105][105];
	cin>>n>>m;
    for (int i=1;i<=n;i++){
    	for (int j=1;j<=m;j++){
    		cin>>a[i][j];
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (a[i][j]==1){
				add(S,calc(i,j),19260817);
				add(calc(i,j),S,0);
			}
			if (a[i][j]==2){
				add(calc(i,j),T,19260817);
				add(T,calc(i,j),0);
			}
			if (i<n){
				add(calc(i,j),calc(i+1,j),1);
				add(calc(i+1,j),calc(i,j),0);
			}
			if (i>1){
				add(calc(i,j),calc(i-1,j),1);
				add(calc(i-1,j),calc(i,j),0);
			}
			if (j<m){
				add(calc(i,j),calc(i,j+1),1);
				add(calc(i,j+1),calc(i,j),0);
			}
			if (j>1){
				add(calc(i,j),calc(i,j-1),1);
				add(calc(i,j-1),calc(i,j),0);
			}
		}
	}
    bfs(S,T);
    cout<<dinic(S,T);
}
暂无评论

发送评论 编辑评论


				
上一篇
下一篇