DDOSvoid's Blog

The 2021 ICPC Asia Shenyang Regional Contest D Cross the Maze

发表于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟

题目描述

http://codeforces.com/gym/103427/problem/D

简要题意：给定一个 $a\times b$ 的四连通网格图，有 $n$ 个起点和 $n$ 个终点，现在有 $n$ 个人来到这 $n$ 个起点，同一时间不能有两个人在同一个点，每个时刻每个人可以选择移动或者停止，一个人来到终点可以随时选择离开，每个终点只能使用一次，求最少多长时间所有人都离开

$a\times b \le 100,n\le 100$

Solution

注意到最多需要花 $a\times b$ 的时间，我们考虑二分时间 $t$，然后将每个位置拆成 $(t+1)$ 个时间，拆点之后因为每个点只能经过一次，所以还要再拆一次

至于输出路径，因为所有边的容量都为 $1$，所以我们直接对于所有起点 $dfs$ 即可，路径是唯一的

建图：

$s$ 连 $(s_x,s_y,0)$，容量为 $1$

对于所有 $k\in[0,t]$，$(x_u,y_u,k)$ 连 $(x_u,y_u,k)’$，容量为 $1$

对于所有 $k\in [0,t-1]$，$(x_u,y_u,k)’$ 连 $(x_{v},y_{v},k+1)$，容量为 $1$

$(x_u,y_u,t)$ 连 $t$，容量为 $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
139
140
#include <iostream>
#include <queue>
#include <tuple>
#define maxn 22010
#define maxm 110
#define INF 1000000000
using namespace std;

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
char ch[] = { 'R', 'L', 'D', 'U' };

int n, m, k;
bool st[maxm][maxm], ed[maxm][maxm];

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

struct Edge {
    int to, next, w;
} e[10000000]; 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], s, t; 
bool bfs() {
    queue<int> Q; Q.push(s); 
    fill(dep, dep + maxn, 0); dep[s] = 1; 
    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 (!_w || u == t) 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; 
} 

bool check(int T) {
    s = 0; t = 2 * n * m * (T + 1) + 1;
    for (int i = s; i <= t; ++i) head[i] = -1; c1 = 0; 
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) 
            for (int k = 0; k <= T; ++k) {
                if (st[i][j] && k == 0) Add_edge(s, id(i, j, k), 1);
                if (ed[i][j] && k == T) Add_edge(id(i, j, k) + n * m * (T + 1), t, 1);
                Add_edge(id(i, j, k), id(i, j, k) + n * m * (T + 1), 1);
                if (k < T) Add_edge(id(i, j, k) + n * m * (T + 1), id(i, j, k + 1), 1);
                for (int p = 0; p < 4; ++p) {
                    int x = i + dx[p], y = j + dy[p];
                    if (x < 1 || x > n || y < 1 || y > m) continue;
                    if (k < T) Add_edge(id(i, j, k) + n * m * (T + 1), id(x, y, k + 1), 1); 
                }
            }
    return dinic() == ::k;
}

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

vector<pair<int, int>> vec;
void dfs(int u) {
    if (u == t) return ; vec.push_back(Id(u));
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w; if (w || (i & 1)) continue;
        dfs(v);
    } 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> k >> n >> m;
    for (int i = 1; i <= k; ++i) {
        int x, y; cin >> x >> y;
        st[x][y] = 1; 
    }
    for (int i = 1; i <= k; ++i) {
        int x, y; cin >> x >> y;
        ed[x][y] = 1;
    }
    int l = 1, r = n * m, mid, ans;
    while (l <= r)  {
        mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1; 
    } check(ans); cout << ans << "\n";
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (!st[i][j]) continue; vector<char> res;
            vec.clear(); dfs(id(i, j, 0)); 
            cout << i << " " << j << " " << vec.back().first << " " << vec.back().second << " ";
            for (int i = 1; i < vec.size(); i += 2) {
                for (int k = 0; k < 4; ++k) 
                    if (vec[i].first + dx[k] == vec[i + 1].first &&
                        vec[i].second + dy[k] == vec[i + 1].second) res.push_back(ch[k]);
                if (vec[i] == vec[i + 1]) res.push_back('S');
            }
            for (auto ch : res) cout << ch; 
            for (int i = 1; i <= ans - res.size(); ++i) cout << 'P';
            cout << "\n";
        }
    return 0;
}