yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P3355 骑士共存问题

发表于 更新于 分类于

P3355 骑士共存问题

题面

题目链接

解法

显然是一个二分图最小割问题。

如果不考虑障碍，可以直接源点到左边点、右边点到汇点连$1$的边，而左右点之间冲突的连$+\infty$。

现在考虑障碍物。思考之前建图的意义，一个点和源点/汇点之间的边被割掉代表不取这个点。于是这些障碍物显然不能取，所以干脆不将它们连边，最后答案在$n \times n - mincut$的基础上再减去$m$就可以了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/**
 * @file:           P3355.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P3355
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
template <const int MAXV, const int MAXE>
struct Dinic {
    const int INF = 0x3f3f3f3f3f3f3f3f;
    struct Edge {
        int v, flow;
    } edge[MAXE * 2];
    int tot = 1, flow = 0;
    int head[MAXV], lev[MAXV], cur[MAXV], nxt[MAXE * 2];
    void addedge(int u, int v, int flow) {
        edge[++tot] = {v, flow};
        nxt[tot] = head[u], head[u] = tot;
        edge[++tot] = {u, 0};
        nxt[tot] = head[v], head[v] = tot;
    }
    bool bfs(int s, int t) {
        fill(lev, lev + MAXV, -1);
        queue<int> que;
        que.push(s);
        lev[s] = 0;
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i = head[u]; i; i = nxt[i]) {
                int v = edge[i].v;
                if (edge[i].flow && lev[v] == -1) {
                    lev[v] = lev[u] + 1;
                    que.push(v);
                }
            }
        }
        return lev[t] != -1;
    }
    int augment(int u, int t, int mx) {
        if (u == t || mx == 0)
            return mx;
        int ret = 0;
        for (int &i = cur[u]; i; i = nxt[i]) {
            int v = edge[i].v;
            if (lev[v] != lev[u] + 1)
                continue;
            int tmp = augment(v, t, min(mx, edge[i].flow));
            mx -= tmp, ret += tmp;
            edge[i].flow -= tmp, edge[i ^ 1].flow += tmp;
            if (mx == 0)
                break;
        }
        return ret;
    }
    int maxflow(int s, int t) {
        while (bfs(s, t)) {
            copy(head, head + MAXV, cur);
            flow += augment(s, t, INF);
        }
        return flow;
    }
};
const int MAXN = 205;
const int MAXV = 4e4 + 10;
const int MAXE = 4e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int DX[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int DY[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int n, m, s, t, num, mp[MAXN][MAXN], pt[MAXN][MAXN];
Dinic<MAXV, MAXE> network;
signed main() {
    read(n), read(m);
    for (int i = 1; i <= m; ++i) {
        int x, y;
        read(x), read(y);
        mp[x][y] = true;
    }
    s = ++num, t = ++num;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            pt[i][j] = ++num;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (mp[i][j])
                continue;
            if ((i ^ j) & 1)
                network.addedge(s, pt[i][j], 1);
            else
                network.addedge(pt[i][j], t, 1);
            for (int k = 0; k < 8; ++k) {
                int x = i + DX[k];
                int y = j + DY[k];
                if (x < 1 || y < 1 || x > n || y > n)
                    continue;
                if (mp[x][y])
                    continue;
                if ((i ^ j) & 1)
                    network.addedge(pt[i][j], pt[x][y], INF);
            }
        }
    }
    int ans = n * n - m - network.maxflow(s, t);
    write(ans), putchar('\n');
    return 0;
}