网站开发前端是什么,建设集团有限公司,公司注册信息查询,网站图片加载优化正题
评测记录#xff1a; https://www.luogu.org/recordnew/lists?uid52918pidP2598 大意
有n*m的矩阵#xff0c;里面有羊和狼(也有可能是空)#xff0c;可以在两个格子之间围上篱笆让两个格子不能互相到达#xff0c;要求狼的格子不能和羊的格子在同一个联通块…正题
评测记录 https://www.luogu.org/recordnew/lists?uid52918pidP2598 大意
有n*m的矩阵里面有羊和狼(也有可能是空)可以在两个格子之间围上篱笆让两个格子不能互相到达要求狼的格子不能和羊的格子在同一个联通块上。求最少篱笆数。 解题思路
将每一个格子当成一个点然后相邻的格子连接1表示可以相互到达并可以用篱笆代价1阻隔然后源点连狼inf汇点连羊inf不可以去掉之后求最小割。
构图 代码
#includecstdio
#includecstring
#includealgorithm
#define MN 10005
#define inf 2147483647
using namespace std;
struct line{int to,w,next;
}a[MN*10];
int n,m,c,ls[MN],d[MN],maxs,e;
int head,tail,state[MN],tot,s;
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;a[tot].tox;a[tot].nextls[y];a[tot].w0;ls[y]tot;
}
int num(int x,int y)
{if (x1||y1||xn||ym) return e1;else return (x-1)*my;
}
bool bfs()
{head0;tail1;memset(d,-1,sizeof(d));d[s]0;state[1]s;do{head;int xstate[head];for (int qls[x];q;qa[q].next){int ya[q].to;if (a[q].w0 d[y]-1){d[y]d[x]1;state[tail]y;if (ye) return true;}}}while (headtail);return false;
}
int dinic(int x,int flow)
{int rest0,k;if (xe) return flow;for (int qls[x];q;qa[q].next){int ya[q].to;if (a[q].w0 d[y]d[x]1){rest(kdinic(y,min(a[q].w,flow-rest)));a[q].w-k;a[q^1].wk;if (restflow) return flow;}}if (!rest) d[x]0;return rest;
}
int main()
{tot2;scanf(%d%d,n,m);snum(n,m)1;es1;for (int i1;in;i)for (int j1;jm;j){scanf(%d,c);addl(num(i,j),num(i1,j),1);addl(num(i,j),num(i,j1),1);addl(num(i,j),num(i-1,j),1);addl(num(i,j),num(i,j-1),1);//与周围连边if (c1) addl(s,num(i,j),inf);//狼if (c2) addl(num(i,j),e,inf);//羊}while (bfs()) maxsdinic(s,inf);printf(%d,maxs);
}
