书法 wordpress,网站优化哪里好,wordpress更换目录,做视频网站怎么备案牛牛防疫情
题意#xff1a;
牛牛用卖烤串赚的钱买了一款游戏#xff0c;这款游戏的地图是一个 n*n 的网格#xff0c;其中有 m 个地区存在感染源#xff08;红色#xff09;#xff0c;其余地区为安全区#xff08;白色#xff09;。已知一个感染源可同时将与其相邻…牛牛防疫情
题意
牛牛用卖烤串赚的钱买了一款游戏这款游戏的地图是一个 n*n 的网格其中有 m 个地区存在感染源红色其余地区为安全区白色。已知一个感染源可同时将与其相邻上下左右的安全区感染被感染的安全区称之为新发地黄色。一个安全区变为一个新发地需要付出大小为 c 的代价。新发地可在下一时刻作为感染源将与其相邻的安全区感染为新的新发地。 为了遏制疫情扩散牛牛决定采取下列两种措施
在感染源新发地周围修建墙墙可阻止疫情的扩散。但每堵墙需要付出大小为 1 的代价。任意让疫情扩散。
牛牛现在想知道采取哪种措施可以使得付出的代价最小。
题解
对于每个格子要么被感染要么被墙隔离 我们可以想最小割认为与s相连的是被感染的与t相连的是被隔离的 如何建边 源点连向每一个感染源流量为正无穷 非感染源向T连流量为c 相邻格子之间连流量为1 这样如果一个格子最后不被感染那么与相邻的被感染的格子之间的边就需要割掉(不再与s相连)如果被感染就要与T之间的边割掉(不再属于隔离) 题目问最小代价就是最小割 为了方便实验我们代码中是将所有点连接T最后答案再减去初始m个感染源的代价
代码
#include bits/stdc.h
using namespace std;
const long long inf2005020600;
int n,m,s,t,u,v;
long long w,ans,dis[520010];
int tot1,now[520010],head[520010]; struct node {int to,net;long long val;
} e[520010];inline void add(int u,int v,long long w) {e[tot].tov;e[tot].valw;e[tot].nethead[u];head[u]tot;e[tot].tou;e[tot].val0;e[tot].nethead[v];head[v]tot;
}inline int bfs() { //在惨量网络中构造分层图memset(dis,0x3f3f3f3f3f3f3f3f,sizeof dis);
// for( int i1;in*n4;i) dis[i]inf;queueint q;q.push(s);dis[s]0;now[s]head[s];while(!q.empty()) {int xq.front();q.pop();for(int ihead[x];i;ie[i].net) {int ve[i].to;if(e[i].val0dis[v]0x3f3f3f3f3f3f3f3f) {q.push(v);now[v]head[v];dis[v]dis[x]1;if(vt) return 1;}}}return 0;
}inline int dfs(int x,long long sum) { //sum是整条增广路对最大流的贡献if(xt) return sum;long long k,res0; //k是当前最小的剩余容量 for(int inow[x];isum;ie[i].net) {now[x]i; //当前弧优化 int ve[i].to;if(e[i].val0(dis[v]dis[x]1)) {kdfs(v,min(sum,e[i].val));if(k0) dis[v]inf; //剪枝去掉增广完毕的点 e[i].val-k;e[i^1].valk;resk; //res表示经过该点的所有流量和相当于流出的总量 sum-k; //sum表示经过该点的剩余流量 }}return res;
}
int dx[]{0,0,0,-1,1};
int dy[]{0,-1,1,0,0};
int main() {int c;scanf(%d%d%d,n,m,c);sn*n1;tn*n2;for(int i1;im;i){int x,y;scanf(%d%d,x,y);x,y;int pos(x-1)*ny;add(s,pos,1e9);
// add(pos,S,0);}for(int i1;in;i){for(int j1;jn;j){int pos(i-1)*nj;add(pos,t,c);for(int k1;k4;k){int xidx[k];int yjdy[k];if(x1xny1yn)add(pos,(x-1)*ny,1);}}} while(bfs()) {ansdfs(s,inf); //流量守恒流入流出 }printf(%lld,ans-c*m);return 0;
}
