题解 | #牛牛防疫情#

题目大意

有一个n*n的网格，现在已经有若干点已经被感染了，每个感染点会对旁边的点进行扩散，每新增一个感染点就有c点代价

或者可以在两个点之间以1点代价建一堵墙，可以防止两个点之间的直接扩散（如果旁边没建那可能会从旁边绕过来）

现在让你求最小代价

解题思路

数据不是很大，可以考虑用网络流最小割

从s对每个感染点建inf的连边（可以无限扩散），对相邻的点之间建一条双向度为1的边（用1的代价可以防止扩散，因为墙的两边分别是感染和未感染的，所以建双向边不会有问题），再让所有原来未感染的点对t连一条c的边（感染代价为c）

建完图后跑最小割即可得到最小代价

code

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 40010
using namespace std;
const int inf=2147483647;
int n,m,c,s,t,x,y,ans,tot,h[N],d[N];
struct rec
{
    int to,nx,edge;
}e[N*15];
void add(int x,int y,int z)
{
    e[++tot].to=y;
    e[tot].edge=z;
    e[tot].nx=h[x];
    h[x]=tot;

    e[++tot].to=x;
    e[tot].edge=0;
    e[tot].nx=h[y];
    h[y]=tot;
}
queue<int>q;
int g(int x,int y)
{
    return (x-1)*n+y;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    d[s]=1;
    while(!q.empty())q.pop();
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=e[i].nx){
            int v=e[i].to;
            if(!d[v]&&e[i].edge){
                d[v]=d[u]+1;
                if(v==t)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int dfs(int x,int flow)
{
    if(x==t)return flow;
    int rest=0,k,y;
    for(int i=h[x];i;i=e[i].nx){
        y=e[i].to;
        if(d[y]!=d[x]+1||!e[i].edge)continue;
        k=dfs(y,min(flow-rest,e[i].edge));
        if(!k)d[y]=0;
        rest+=k;
        e[i].edge-=k;
        e[i^1].edge+=k;
        if(rest==flow)return rest;
    }
    return rest;
}
int main()
{
    scanf("%d%d%d",&n,&m,&c);
    s=n*n+1;
    t=n*n+2;
    tot=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            if(j<n){
                add(g(i,j),g(i,j+1),1);
                add(g(i,j+1),g(i,j),1);
            }
            if(i<n){
                add(g(i,j),g(i+1,j),1);
                add(g(i+1,j),g(i,j),1);
            }
            add(g(i,j),t,c);
        }
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        x++;
        y++;
        add(s,g(x,y),inf);
    }
    while(bfs())
        ans+=dfs(s,inf);//最小割
    printf("%d",ans-m*c);
    return 0;
}