Description

　　“狼愛上羊啊愛的瘋狂，誰讓他們真愛了一場；狼愛上羊啊并不荒唐，他們說有愛就有方向．．．．．．”
　　Orez聽到這首歌，心想：狼和羊如此和諧，為什么不嘗試羊狼合養呢？說干就干！
　　Orez的羊狼圈可以看作一個n*m個矩陣格子，這個矩陣的邊緣已經裝上了籬笆。可是Drake很快發現狼再怎么也是狼，它們總是對羊垂涎三尺，那首歌只不過是一個動人的傳說而已。所以Orez決定在羊狼圈中再加入一些籬笆，還是要將羊狼分開來養。
　　通過仔細觀察，Orez發現狼和羊都有屬于自己領地，若狼和羊們不能呆在自己的領地，那它們就會變得非常暴躁，不利于他們的成長。
　　Orez想要添加籬笆的盡可能的短。當然這個籬笆首先得保證不能改變狼羊的所屬領地，再就是籬笆必須修筑完整，也就是說必須修建在單位格子的邊界上并且不能只修建一部分。

Input

　　輸入數據存放在文本文件ws.in中。
　　文件的第一行包含兩個整數n和m。接下來n行每行m個整數，1表示該格子屬于狼的領地，2表示屬于羊的領地，0表示該格子不是任何一只動物的領地。

Output

　　輸出數據存放在文本文件ws.out中。
　　文件中僅包含一個整數ans，代表籬笆的最短長度。

Sample Input

2 2
2 2
1 1

Sample Output

2

Data Constraint

Hint

【數據范圍】

　　10%的數據 n，m≤3
　　30%的數據 n，m≤20
　　100%的數據 n，m≤100

Solution

• 挖掘柵欄的本質：只能建在相鄰兩個，且建好后使得狼和羊之間不存在通路。

• 而割的定義是：使 S 集和 T 集不存在通路。而題目又要求建的柵欄最少，于是就是最小割問題了。

• 從源點向所有狼連一條 +∞ 的邊，從所有羊向匯點連一條 +∞ 的邊，

• 這樣就能保證狼和羊都在不同的點集里。

• 然后再從狼到相鄰的羊和空地，空地到相鄰的空地和羊連一條流量為1的邊，最大流求最小割即可。

Code

#include<cstdio> #include<cctype> using namespace std; const int N=101,M=N*N,inf=1e9,way[4][2]={{1,0},{0,1},{0,-1},{-1,0}}; int s,t,n,m,p,num,ans,tot=1; int first[M],next[M<<3],en[M<<3],w[M<<3]; int dis[M],gap[M],cur[M],a[N][N],b[N][N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int min(int x,int y) {return x<y?x:y; } inline void insert(int x,int y,int z) {next[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline int sap(int x,int y) {if(x==t) return y;int use=0;for(int i=cur[x];i;i=next[i])if(w[i] && dis[x]==dis[en[i]]+1){cur[x]=i;int sum=sap(en[i],min(w[i],y-use));use+=sum,w[i]-=sum,w[i^1]+=sum;if(use==y || dis[s]>p) return use;}cur[x]=first[x];if(!--gap[dis[x]]) dis[s]=p+1;gap[++dis[x]]++;return use; } int main() {n=read(),m=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) a[i][j]=read(),b[i][j]=++num;s=num+1,t=num+2;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]<2)for(int k=0;k<4;k++){int x=i+way[k][0],y=j+way[k][1];if(x<1 || x>n || y<1 || y>m || a[x][y]==1) continue;insert(b[i][j],b[x][y],1);insert(b[x][y],b[i][j],0),p++;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]==1) insert(s,b[i][j],inf),insert(b[i][j],s,0),p++; elseif(a[i][j]==2) insert(b[i][j],t,inf),insert(b[i][j],t,0),p++;for(int i=1;i<=num;i++) cur[i]=first[i];gap[0]=p;while(dis[s]<=p) ans+=sap(s,inf);printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 1637. 【ZJOI2009】狼和羊的故事的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。