P2598 [ZJOI2009]狼和羊的故事

题目描述

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

输入格式

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

输出格式

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

题解：
将狼和羊分开，考虑最小割建图，而且我们不能割掉狼或者羊，所以建图将所有羊连向源点，设流量为INF，狼同样连向汇点，设流量为INF，表示狼和羊都不能被割掉，然后对于每个点都向四周连流量为1的边跑最小割让它自己取舍…hhhhh…

AC代码：

#pragma GCC optimize(2)
#include
#include
using namespace std;
using namespace __gnu_cxx;
#define LL long long
const int MAXN = 20000+50;
const int MAXM = 2e6+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int n,m,s,t,tot=1,head[MAXN],to[MAXM],nxt[MAXM],w[MAXM],h[MAXN];
int dir[][2]={{1,0},{-1,0},{0,1},{0,-1}};
inline void ade(int u,int v,int ww){to[++tot]=v; w[tot]=ww; nxt[tot]=head[u]; head[u]=tot;
}
inline void add(int u,int v,int w){ ade(u,v,w); ade(v,u,0); }
inline int bfs(){queue<int> que; que.push(s); memset(h,0,sizeof(h)); h[s]=1;while(!que.empty()){int u=que.front(); que.pop();for(int i=head[u];i;i=nxt[i]){if(w[i] && !h[to[i]]){h[to[i]]=h[u]+1; que.push(to[i]);}}}return h[t];
}
inline int dfs(int x,int f){if(x==t) return f; int fl=0;for(int i=head[x];i&&f;i=nxt[i]){if(w[i] && h[to[i]]==h[x]+1){int mi=dfs(to[i],min(f,w[i]));w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;}}if(!fl) h[x]=-1;return fl;
}
inline int dinic(){int res=0;while(bfs()) res+=dfs(s,INF);return res;
}
signed main(){
#ifndef ONLINE_JUDGEfreopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGEscanf("%d%d",&n,&m); s=0,t=n*m+1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int op; scanf("%d",&op);if(op==1) add(s,(i-1)*m+j,INF);else if(op==2) add((i-1)*m+j,t,INF);for(int k=0;k<4;k++){int x=i+dir[k][0],y=j+dir[k][1];if(x>=1 && x<=n && y>=1 && y<=m) add((i-1)*m+j,(x-1)*m+y,1);}}}printf("%d\n",dinic());return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！