C++の練習を兼ねて, AtCoder Beginner Contest 205 の 問題F (Grid and Tokens) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. Dinic法に触れることが出来たので, 非常に良かったと思う.
※ 競プロ典型 90 問のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 205 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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 |
// 解き直し. // https://atcoder.jp/contests/abc205/editorial/2057 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using P = pair<int, int>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back const int MAX = 2020; int PA[101], PB[101], PC[101], PD[101]; struct Edge{ int to, cap, rev; }; // Dinic // https://github.com/E869120/kyopro_educational_90/blob/main/sol/077-04a.cpp // -> 一部改変(2022/04/23). struct Dinic{ int size_; vi level, iter; vector<Edge> G[MAX]; Dinic(int n = 0) : size_(n), level(n + 1), iter(n + 1) {} void edge(int u, int v, int c){ G[u].pb(Edge{v, c, (int)G[v].size()}); G[v].pb(Edge{u, 0, (int)G[u].size() - 1}); } void bfs(int s){ rep(i, size_ + 1) level[i] = -1; queue<int> q; q.push(s); level[s] = 0; while(!q.empty()){ int pos = q.front(); q.pop(); rep(i, G[pos].size()){ if(G[pos][i].cap == 0 || level[G[pos][i].to] != -1) continue; q.push(G[pos][i].to); level[G[pos][i].to] = level[pos] + 1; } } } int dfs(int pos, int to, int f){ if(pos == to) return f; for(int& i = iter[pos]; i < G[pos].size(); i++){ if(G[pos][i].cap > 0 && level[pos] < level[G[pos][i].to]){ int z = dfs(G[pos][i].to, to, min(f, G[pos][i].cap)); if(z > 0){ G[pos][i].cap -= z; G[G[pos][i].to][G[pos][i].rev].cap += z; return z; } } } return 0; } int maxFlow(int s, int t){ int ret = 0; while(1){ bfs(s); if(level[t] == -1) break; rep(i, size_ + 1) iter[i] = 0; while(1){ int f = dfs(s, t, 1000000007); if(f == 0) break; ret += f; } } return ret; } }; int main(){ // 1. 入力情報. int H, W, N; scanf("%d %d %d", &H, &W, &N); rep(i, N) scanf("%d %d %d %d", &PA[i], &PB[i], &PC[i], &PD[i]); rep(i, N){ PB[i] += H; PD[i] += H; } // 2. グラフ構築(解説通り). // -> 頂点番号は, 以下のように設定. // src = 0 // R = 1 ～ H // C = H + 1 ～ H + W // U = H + W + 1 ～ H + W + N // V = H + W + N + 1 ～ H + W + N + N // dst = H + W + N + N + 1 // int src = 0, dst = H + W + N + N + 1; Dinic D(H + W + N + N + 5); repx(r, 1, H + 1) D.edge(src, r, 1); rep(i, N){ int u = H + W + i + 1; repx(r, PA[i], PC[i] + 1) D.edge(r, u, 1); } rep(i, N){ int u = H + W + i + 1; int v = H + W + N + i + 1; D.edge(u, v, 1); } rep(i, N){ int v = H + W + N + i + 1; repx(c, PB[i], PD[i] + 1) D.edge(v, c, 1); } repx(c, H + 1, H + W + 1) D.edge(c, dst, 1); // 3. 出力. printf("%d\n", D.maxFlow(src, dst)); return 0; } |
|
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 |
[入力例] 2 3 3 1 1 2 2 1 2 2 3 1 1 1 3 [出力例] 2 ※AtCoderテストケースより [入力例] 5 5 3 1 1 5 5 1 1 4 4 2 2 3 3 [出力例] 3 ※AtCoderテストケースより [入力例] 2 2 2 1 1 1 1 1 1 2 2 [出力例] 2 [入力例] 7 10 12 3 3 6 4 3 3 5 5 3 8 4 10 2 9 5 10 3 3 5 5 2 7 3 8 3 8 3 10 2 9 7 10 3 4 5 5 3 5 5 5 2 3 3 6 2 9 6 10 [出力例] 6 [入力例] 12 15 18 5 4 7 7 5 5 6 6 5 4 7 8 4 5 5 7 3 5 9 6 3 6 10 6 3 5 9 7 2 6 8 7 2 7 7 8 2 8 7 9 1 6 5 7 1 5 6 7 1 6 7 9 1 3 3 4 1 5 2 6 10 12 12 12 10 12 11 13 10 11 11 13 [出力例] 10 |