网站风格对比信息表,西安的商城网站设计,wordpress手机站和pc如何切换的,个人小程序P2598 [ZJOI2009]狼和羊的故事 题目描述 “狼爱上羊啊爱的疯狂#xff0c;谁让他们真爱了一场#xff1b;狼爱上羊啊并不荒唐#xff0c;他们说有爱就有方向#xff0e;#xff0e;#xff0e;#xff0e;#xff0e;#xff0e;” Orez听到这首歌#xff0c;心想谁让他们真爱了一场狼爱上羊啊并不荒唐他们说有爱就有方向” Orez听到这首歌心想狼和羊如此和谐为什么不尝试羊狼合养呢说干就干 Orez的羊狼圈可以看作一个n*m个矩阵格子这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼它们总是对羊垂涎三尺那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆还是要将羊狼分开来养。 通过仔细观察Orez发现狼和羊都有属于自己领地若狼和羊们不能呆在自己的领地那它们就会变得非常暴躁不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地再就是篱笆必须修筑完整也就是说必须修建在单位格子的边界上并且不能只修建一部分。 输入输出格式 输入格式 文件的第一行包含两个整数n和m。接下来n行每行m个整数1表示该格子属于狼的领地2表示属于羊的领地0表示该格子不是任何一只动物的领地。 输出格式 文件中仅包含一个整数ans代表篱笆的最短长度。 分析 要保证篱笆长最小而把狼和羊分开来我们可以联想到最小割模型。一个图的最小割就是把图分为两个部分源点及汇点不在同一部的边权和。最小割可以用最大流算法求得。 建模 要说到网络流重点就在于建模了我们怎么把此网格图转换为最大流网络流呢其实对于一个格子我们可以把它看做与上下左右四个方向都有一条连边而把这个格子抽象成一个点如下图 依据题意和最大流的经验我们可以连边了我以羊的一部作为源点所以源点连羊狼连汇点若相邻的点事狼则连一条容量为1的边他的模型意义是把羊和狼分开【割】需要消耗“1” 但是对于0怎么办呢这是本题的难点 可以思索一下若是把0全部归为狼或者羊吧感觉又会有更优解事实也是这样因为狼和羊是等价的【把狼从羊中隔离开来等价于把羊从狼中隔离开来】所以这样单方面划分是肯定不正确的那么怎么办呢 你可能不会但你的最大流算法一定知道怎么做 我们这样连源点---羊--边Ac1--0--边B, c1--狼---汇点 试想一下你的篱笆的作用是分割狼和羊0这些格子要么被划分到狼的领地要么被划分到羊的领地若是划分到狼那边你的算法会割开靠近羊的那条边 A 要是划分到羊这边他会自动割开靠近狼的边 B 。一定不存在一种割的方式使 A 和 B 同时被割开因为你的算法知道割一条就足以分开两点不需要割第二条。 所以放手给程序去跑吧 Code #includeiostream
#includecstdio
#includequeue
#includecstring
#includealgorithm
#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(){queueintQ;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;} 转载于:https://www.cnblogs.com/Tony-Double-Sky/p/9285535.html
