牛牛防疫情

題意：

牛牛用賣烤串賺的錢買了一款游戲，這款游戲的地圖是一個 n*n 的網(wǎng)格，其中有 m 個地區(qū)存在感染源（紅色），其余地區(qū)為安全區(qū)（白色）。已知一個感染源可同時將與其相鄰（上下左右）的安全區(qū)感染，被感染的安全區(qū)稱之為新發(fā)地（黃色）。一個安全區(qū)變?yōu)橐粋€新發(fā)地需要付出大小為 c 的代價。新發(fā)地可在下一時刻作為感染源將與其相鄰的安全區(qū)感染為新的新發(fā)地。
為了遏制疫情擴散，牛牛決定采取下列兩種措施

在感染源（新發(fā)地）周圍修建墻，墻可阻止疫情的擴散。但每堵墻需要付出大小為 1 的代價。

任意讓疫情擴散。

牛牛現(xiàn)在想知道采取哪種措施可以使得付出的代價最小。

題解：

對于每個格子要么被感染，要么被墻隔離，
我們可以想最小割，認為與s相連的是被感染的，與t相連的是被隔離的
如何建邊？
源點連向每一個感染源，流量為正無窮；
非感染源向T連流量為c
相鄰格子之間連流量為1
這樣如果一個格子最后不被感染，那么與相鄰的被感染的格子之間的邊就需要割掉(不再與s相連)；如果被感染，就要與T之間的邊割掉(不再屬于隔離)
題目問最小代價，就是最小割
為了方便實驗，我們代碼中是將所有點連接T，最后答案再減去初始m個感染源的代價

代碼：

#include <bits/stdc++.h> using namespace std; const long long inf=2005020600; int n,m,s,t,u,v; long long w,ans,dis[520010]; int tot=1,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].to=v;e[tot].val=w;e[tot].net=head[u];head[u]=tot;e[++tot].to=u;e[tot].val=0;e[tot].net=head[v];head[v]=tot; }inline int bfs() { //在慘量網(wǎng)絡中構(gòu)造分層圖memset(dis,0x3f3f3f3f3f3f3f3f,sizeof dis); // for( int i=1;i<=n*n+4;i++) dis[i]=inf;queue<int> q;q.push(s);dis[s]=0;now[s]=head[s];while(!q.empty()) {int x=q.front();q.pop();for(int i=head[x];i;i=e[i].net) {int v=e[i].to;if(e[i].val>0&&dis[v]==0x3f3f3f3f3f3f3f3f) {q.push(v);now[v]=head[v];dis[v]=dis[x]+1;if(v==t) return 1;}}}return 0; }inline int dfs(int x,long long sum) { //sum是整條增廣路對最大流的貢獻if(x==t) return sum;long long k,res=0; //k是當前最小的剩余容量 for(int i=now[x];i&&sum;i=e[i].net) {now[x]=i; //當前弧優(yōu)化 int v=e[i].to;if(e[i].val>0&&(dis[v]==dis[x]+1)) {k=dfs(v,min(sum,e[i].val));if(k==0) dis[v]=inf; //剪枝，去掉增廣完畢的點 e[i].val-=k;e[i^1].val+=k;res+=k; //res表示經(jīng)過該點的所有流量和（相當于流出的總量） sum-=k; //sum表示經(jīng)過該點的剩余流量 }}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);s=n*n+1;t=n*n+2;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);x++,y++;int pos=(x-1)*n+y;add(s,pos,1e9); // add(pos,S,0);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int pos=(i-1)*n+j;add(pos,t,c);for(int k=1;k<=4;k++){int x=i+dx[k];int y=j+dy[k];if(x>=1&&x<=n&&y>=1&&y<=n)add(pos,(x-1)*n+y,1);}}} while(bfs()) {ans+=dfs(s,inf); //流量守恒（流入=流出） }printf("%lld",ans-c*m);return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛89--牛牛防疫情的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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