牛牛防疫情

题目链接：nowcoder 225285

到主站看：https://blog.csdn.net/weixin_43346722/article/details/120521191

题目大意

给你一个二维网格图，然后有一些特殊点，它每隔一个时刻让它四边的点变成特殊点。
然后你可以在两个点之间建一个屏障使得无法转变。
然后使得一个普通点变成特殊点要费用 c，建立屏障是要 1 费用。
要你最小化总费用。

思路

这道题我们考虑用网络流来做。

这么一想之后你就会发现这题确实可以网络流。
相当于搞最小割，所有点向汇点连边流量是 表示被感染，然后本身被感染的点连向源点流量 INF 表示被感染。然后点和它四边之间连边流量是 表示要建护栏。

然后跑最小割就是答案。

代码

#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define INF 1000000000

using namespace std;

struct node {
    int x, to, nxt;
}e[500004];
int n, m, x, y, le[50001], KK, dis[50001], S, T, lee[50001];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int ans, c;

void add(int x, int y, int z) {
    e[++KK] = (node){z, y, le[x]}; le[x] = KK;
    e[++KK] = (node){0, x, le[y]}; le[y] = KK;
}

int get_nm(int x, int y) {
    return (x - 1) * n + y;
}

bool bfs() {//网络流
    queue <int> q;
    memcpy(lee, le, sizeof(lee));
    memset(dis, 0x7f, sizeof(dis));
    dis[S] = 0;
    q.push(S);
    int now;
    while (!q.empty()) {
        now = q.front();
        q.pop();

        for (int i = le[now]; i; i = e[i].nxt)
            if (e[i].x && dis[e[i].to] > dis[now] + 1) {
                dis[e[i].to] = dis[now] + 1;
                q.push(e[i].to);
            }
    }
    return dis[T] < INF;
}

int dfs(int now, int sum) {
    if (now == T) return sum;
    int go = 0, this_go;
    for (int i = lee[now]; i; i = e[i].nxt) {
        lee[now] = i;
        if (e[i].x && dis[e[i].to] == dis[now] + 1) {
            this_go = dfs(e[i].to, min(e[i].x, sum - go));
            if (this_go) {
                e[i].x -= this_go;
                e[i ^ 1].x += this_go;
                go += this_go;
                if (go == sum) return go;
            }
        }
    }
    return go;
}

void dinic() {
    while (bfs()) {
        ans += dfs(S, INF);
    }
}

int main() {
    KK = 1;
    scanf("%d %d %d", &n, &m, &c);

    S = 50000 - 1; T = 50000 - 2;
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y); x++; y++;
        add(S, get_nm(x, y), INF);
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            add(get_nm(i, j), T, c);

            for (int k = 0; k < 4; k++) {
                x = i + dx[k]; y = j + dy[k];
                if (1 <= x && x <= n && 1 <= y && y <= n) {//可以建屏障
                    add(get_nm(i, j), get_nm(x, y), 1);
                }
            }
        }

    dinic();
    printf("%d", ans - c * m);//记得减去本身就已经感染的点

    return 0;
}