P2598 [ZJOI2009]狼和羊的故事

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

輸入輸出格式
輸入格式：
文件的第一行包含兩個整數(shù)n和m。接下來n行每行m個整數(shù)，1表示該格子屬于狼的領(lǐng)地，2表示屬于羊的領(lǐng)地，0表示該格子不是任何一只動物的領(lǐng)地。

輸出格式：
文件中僅包含一個整數(shù)ans，代表籬笆的最短長度。

---

分析

要保證籬笆長最小而把狼和羊分開來，我們可以聯(lián)想到最小割模型。一個圖的最小割就是把圖分為兩個部分（源點及匯點不在同一部）的邊權(quán)和。最小割可以用最大流算法求得。

建模

要說到網(wǎng)絡流，重點就在于建模了，我們怎么把此網(wǎng)格圖轉(zhuǎn)換為最大流網(wǎng)絡流呢？其實對于一個格子，我們可以把它看做與上下左右四個方向都有一條連邊，而把這個格子抽象成一個點，如下圖：

依據(jù)題意和最大流的經(jīng)驗，我們可以連邊了：（我以羊的一部作為源點，所以）源點連羊，狼連匯點，若相鄰的點事狼，則連一條容量為1的邊（他的模型意義是：把羊和狼分開【割】需要消耗“1”）

但是對于0怎么辦呢？這是本題的難點

可以思索一下，若是把0全部歸為狼或者羊吧，感覺又會有更優(yōu)解（事實也是這樣，因為狼和羊是等價的【把狼從羊中隔離開來等價于把羊從狼中隔離開來】，所以這樣單方面劃分是肯定不正確的），那么怎么辦呢

你可能不會，但你的最大流算法一定知道怎么做

我們這樣連：源點---羊--（邊A，c=1）--0--（邊B, c=1）--狼---匯點

試想一下，你的籬笆的作用是分割狼和羊，0這些格子要么被劃分到狼的領(lǐng)地，要么被劃分到羊的領(lǐng)地，若是劃分到狼那邊，你的算法會割開靠近羊的那條邊 A ，要是劃分到羊這邊，他會自動割開靠近狼的邊 B 。一定不存在一種割的方式，使 A 和 B 同時被割開，因為你的算法知道，割一條就足以分開兩點，不需要割第二條。

所以，放手給程序去跑吧

Code

#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> #define ll long long using namespace std; int RD(){int out = 0,flag = 1;char c = getchar();while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}return flag * out;} const int maxn = 100019,INF = 1e9; int nume = 1; int lenx,leny; int map[190][190]; int mx[4] = {1,-1,0,0}; int my[4] = {0,0,1,-1}; int s,t,maxflow; int head[maxn]; struct Node{int v,dis,nxt;}E[maxn << 2]; void add(int u,int v,int dis){E[++nume].nxt = head[u];E[nume].v = v;E[nume].dis = dis;head[u] = nume;} int lev[maxn]; bool bfs(){queue<int>Q;memset(lev,0,sizeof(lev));Q.push(s);lev[s] = 1;while(!Q.empty()){int u = Q.front();Q.pop();for(int i = head[u];i;i = E[i].nxt){int v = E[i].v;if(E[i].dis && !lev[v]){lev[v] = lev[u] + 1;Q.push(v);if(v == t)return 1;}}}return 0;} int Dinic(int u,int flow){if(u == t)return flow;int rest = flow,k;for(int i = head[u];i;i = E[i].nxt){int v = E[i].v;if(E[i].dis && lev[v] == lev[u] + 1 && rest){k = Dinic(v,min(rest,E[i].dis));if(!k)lev[v] = 0;E[i].dis -= k;E[i ^ 1].dis += k;rest -= k;}}return flow - rest;} int getindex(int x,int y){return (x - 1) * leny + y;} bool judge(int x,int y){if(x < 1 || x > lenx || y < 1 || y > leny)return 0;return 1;} /*for(int i = 1;i <= lenx;i++){for(int j = 1;j <= leny;j++){}}*/ void build(){for(int i = 1;i <= lenx;i++){for(int j = 1;j <= leny;j++){if(map[i][j] == 2){add(s,getindex(i,j),INF);add(getindex(i,j),s,0);}else if(map[i][j] == 1){add(getindex(i,j),t,INF);add(t,getindex(i,j),0);}}}for(int i = 1;i <= lenx;i++){for(int j = 1;j <= leny;j++){if(map[i][j] == 2 || map[i][j] == 0){for(int k = 0;k < 4;k++){int nx = i + mx[k],ny = j + my[k];if(!judge(nx,ny))continue;if(map[nx][ny] == 1 || map[nx][ny] == 0){add(getindex(i,j),getindex(nx,ny),1);add(getindex(nx,ny),getindex(i,j),0);}}}}}} int main(){lenx = RD();leny = RD();for(int i = 1;i <= lenx;i++){for(int j = 1;j <= leny;j++){map[i][j] = RD();}}s = lenx * leny + 1,t = s + 1;build();int flow = 0;while(bfs())while(flow = Dinic(s,INF))maxflow += flow;printf("%d\n",maxflow);return 0;}

轉(zhuǎn)載于:https://www.cnblogs.com/Tony-Double-Sky/p/9285535.html

總結(jié)

以上是生活随笔為你收集整理的题解 P2598 【[ZJOI2009]狼和羊的故事】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。