loj6068. 「2017 山东一轮集训 Day4」棋盘 二分图，网络流

时间：2023-03-08 17:45:47
loj6068. 「2017 山东一轮集训 Day4」棋盘 二分图，网络流

loj6068. 「2017 山东一轮集训 Day4」棋盘

链接

https://loj.ac/problem/6068

思路

上来没头绪，后来套算法，套了个网络流

经典二分图

左边横，右边列

先重新算一下行和列，就是他们x相通的的算一个

然后就去掉了障碍的作用

然后每一行贡献是递增的(0,1,2,3,4………)

直接暴力连上每条可能有的流量为1的边就行了

下面的图可能没啥用就是个普通二分图

loj6068. 「2017 山东一轮集训 Day4」棋盘 二分图，网络流

错误

有的数组开小了

有的memset(1e6)

T成40

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 57, M = 3e5 + 7, inf = 0x3f3f3f3f;

int read() {

    int x = 0, f = 1;

    char s = getchar();

    for (; s > '9' || s < '0'; s = getchar())if (s == '-')f = -1;

    for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';

    return x * f;

}

int n, m, S, T, dsr[N * N];

char s[N][N];

struct node {

    int u, v, nxt, cost, flow;

} e[M];

int head[M], tot = 1;

void add_edge(int u, int v, int flow, int cost) {

    e[++tot].v = v, e[tot].u = u;

    e[tot].cost = cost, e[tot].flow = flow, e[tot].nxt = head[u], head[u] = tot;

}

void add(int u, int v, int flow, int cost) {

    add_edge(u, v, flow, cost);

    add_edge(v, u, 0, -cost);

}

int dis[M], vis[M], frm[M];

int spfa() {

    for (int i = 1; i <= T; ++i) dis[i] = inf, vis[i] = 0;

    queue<int> q;

    q.push(S);

    dis[S] = 0;

    while (!q.empty()) {

        int u = q.front();

        q.pop();

        vis[u] = 0;

        for (int i = head[u]; i; i = e[i].nxt) {

            int v = e[i].v;

            if (dis[u] + e[i].cost < dis[v] && e[i].flow > 0) {

                dis[v] = dis[u] + e[i].cost;

                frm[v] = i;

                if (!vis[v]) {

                    q.push(v);

                    vis[v] = 1;

                }

            }

        }

    }

    return dis[T] != inf;

}

int ans, maxflow;

void work() {

    spfa();

    int mn = inf;

    for (int i = T; i != S; i = e[frm[i]].u) mn = min(e[frm[i]].flow, mn);

    for (int i = T; i != S; i = e[frm[i]].u) {

        e[frm[i]].flow -= mn;

        e[frm[i] ^ 1].flow += mn;

        ans += e[frm[i]].cost * mn;

    }

    maxflow += mn;

}

int belong_x[N][N], belong_y[N][N], hav_x[N * N], hav_y[N * N], num_x, num_y;

int main() {

    n = read();

    for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);

    int js = n * n;

    for (int i = 1; i <= n; ++i) {

        for (int j = 1; j <= n; ++j) {

            if (s[i][j] == '#') {

                js--;

                continue;

            }

            belong_x[i][j] = (s[i][j - 1] == '.') ? belong_x[i][j - 1] : ++num_x;

            belong_y[i][j] = (s[i - 1][j] == '.') ? belong_y[i - 1][j] : ++num_y;

            hav_x[belong_x[i][j]]++;

            hav_y[belong_y[i][j]]++;

        }

    }

    S = num_x + num_y + 1, T = num_x + num_y + 2;

    for (int i = 1; i <= num_x; ++i)

        for (int j = 0; j < hav_x[i]; ++j) add(S, i, 1, j);

    for (int i = 1; i <= num_y; ++i)

        for (int j = 0; j < hav_y[i]; ++j) add(i + num_x, T, 1, j);

    for (int i = 1; i <= n; ++i)

        for (int j = 1; j <= n; ++j)

            if (s[i][j] == '.')

                add(belong_x[i][j], num_x + belong_y[i][j], 1, 0);

    for (int i = 1; i <= js; ++i) work(), dsr[i] = ans;

    m = read();

    while (m--) {

        int x = read();

        if (x > js)

            puts("0");

        else

            printf("%d\n", dsr[x]);

    }

    return 0;

}