DDOSvoid's Blog

Luogu P6517 [CEOI2010 day1] alliances

发表于 更新于 分类于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P6517

简要题意：给定一张 $n\times m$ 的四连通网格图，图上的点分为 $5$ 种：空地、精灵、人类、矮人、霍比特人，这四种生物的要求如下：精灵：只需要与一个邻居结盟；人类：需要与两个邻居结盟，且这两个邻居不能在上下或者左右方向；矮人：需要与三个邻居结盟；霍比特人：需要与四个邻居结盟，结盟关系是双向的，且只有相邻两个点才可结盟，请求出任何一种合法方案

$n,m\le 70$

Solution

首先能够想到黑白染色变成二分图

不妨假设对于人类结盟没有必须上下和左右的要求

这时候我们可以直接这样建图，$g[i][j]$ 表示这个 $(i,j)$ 所需要的结盟数量

$s$ 连黑点 $(i,j)$，容量为 $g[i][j]$

黑点 $(i,j)$ 连周围白点，容量为 $1$

白点 $(i,j)$ 连 $t$，容量为 $g[i][j]$

对于人类结盟的要求，我们可以将人类点拆成两个点分别代表上下和左右，各有 $1$ 的容量

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
137
138
#include <iostream>
#include <cstdio>
#include <queue>
#include <tuple>
#define maxn 10010
#define maxm 80
#define INF 1000000000
using namespace std;

int n, m, s, t;

inline int id(int x, int y) { return (x - 1) * m + y; }

inline pair<int, int> Id(int s) {
    if (s > n * m) s -= n * m;
    int x = s / m + 1, y = s % m;
    if (!y) --x, y = m;
    return { x, y };
}

int g[maxm][maxm];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Edge {
    int to, next, w;
} e[1000000]; int c1, head[maxn];
inline void add_edge(int u, int v, int w) {
    e[c1].to = v; e[c1].w = w; 
    e[c1].next = head[u]; head[u] = c1++;
}

inline void Add_edge(int u, int v,  int w) {
    add_edge(u, v, w); add_edge(v, u, 0);
}

int dep[maxn]; 
bool bfs() {
    fill(dep, dep + maxn, 0); dep[s] = 1; 
    queue<int> Q; Q.push(s);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (w > 0 && !dep[v]) {
                dep[v] = dep[u] + 1;
                Q.push(v); if (v == t) return 1; 
            }
        }
    }
    return 0; 
}

int dfs(int u, int _w) {
    if (u == t || !_w) return _w;
    int s = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (w > 0 && dep[v] == dep[u] + 1) {
            int di = dfs(v, min(_w - s, w));
            e[i].w -= di; e[i ^ 1].w += di;
            s += di; if (s == _w) break; 
        }
    }
    if (s < _w) dep[u] = 0;
    return s; 
}

int dinic() {
    int mf = 0;
    while (bfs()) mf += dfs(s, INF);
    return mf;
} 

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; s = 0; t = 2 * n * m + 1;
    int s1 = 0, s2 = 0; 
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) cin >> g[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (i + j & 1) {
                if (g[i][j] == 2) Add_edge(id(i, j), t, 1), Add_edge(id(i, j) + n * m, t, 1); 
                else Add_edge(id(i, j), t, g[i][j]);
                s1 += g[i][j]; 
            }
            else {
                if (g[i][j] == 2) Add_edge(s, id(i, j), 1), Add_edge(s, id(i, j) + n * m, 1); 
                else Add_edge(s, id(i, j), g[i][j]);
                s2 += g[i][j];
                for (int k = 0; k < 4; ++k) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x < 1 || x > n || y < 1 || y > m) continue;
                    int u = id(i, j) + (g[i][j] == 2) * (k < 2) * (n * m);
                    int v = id(x, y) + (g[x][y] == 2) * (k < 2) * (n * m);
                    Add_edge(u, v, 1); 
                }
            } 
        }
    if (s1 != s2) return cout << "Impossible!\n", 0;
    if (dinic() != s1) return cout << "Impossible!\n", 0;
    char ans[4][4], Ans[3 * maxm][3 * maxm];
    for (int x = 1; x <= n; ++x) 
        for (int y = 1; y <= m; ++y) {
            for (int i = 1; i <= 3; ++i)
                for (int j = 1; j <= 3; ++j) ans[i][j] = '.';
            if (g[x][y]) ans[2][2] = 'O'; bool f = x + y & 1; 
            int u = id(x, y); 
            for (int i = head[u]; ~i; i = e[i].next) {
                int v = e[i].to, w = e[i].w;
                if (v != t && v != s && w == f) {
                    int l, r; tie(l, r) = Id(v);
                    l -= x; r -= y; ans[2 + l][2 + r] = 'X'; 
                }
            }
            if (g[x][y] == 2) {
                u += n * m;
                for (int i = head[u]; ~i; i = e[i].next) {
                    int v = e[i].to, w = e[i].w;
                    if (v != t && v != s && w == f) {
                        int l, r; tie(l, r) = Id(v);
                        l -= x; r -= y; ans[2 + l][2 + r] = 'X'; 
                    }
                }
            }
            for (int i = 3 * (x - 1) + 1; i <= 3 * x; ++i)
                for (int j = 3 * (y - 1) + 1; j <= 3 * y; ++j)
                    Ans[i][j] = ans[i - 3 * (x - 1)][j - 3 * (y - 1)];
        }
    for (int i = 1; i <= 3 * n; ++i, cout << "\n")
        for (int j = 1; j <= 3 * m; ++j) cout << Ans[i][j];
    return 0;
}