ACM/ICPC 2011 成都现场赛 Eliminate the Conflict 题解
在做这题之前还不知道什么是 2-SAT 的。折腾了大半天的，终于写完了。这道题我是 2 次 AC, 问题出在判断剪刀石头布谁能赢的函数写错了……
有关 2-SAT 的资料网上挺多的，解决的方法可以是强连通分量，这道题重点在构图。网上有说每局状态用 6 个顶点代表的方法，也提到“官方”题解是用 2 个顶点的。[AMB'11]
我使用的是每局用两个顶点代表状态的方法，其实也没有多复杂，用了一些 swap 小技巧，就只分了 4 类讨论。
还有一个就是判断两个顶点是否属于同一个强连通分量的时候，我居然用了并查集，这是杀鸡用牛刀了。
本题源代码
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 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 | #include <cstdio> #include <cassert> #include <cstring> #include <algorithm> using namespace std; const int RN = 11111; const int N = 2 * RN; const int M = 4 * RN; struct item_t { int x; item_t() : x(0) { } item_t(int x) : x(x) { } }; inline bool operator>=(item_t a, item_t b) { if (a.x == 1 && b.x == 3) return true; if (b.x == 1 && a.x == 3) return false; return a.x >= b.x; } struct glist { int m, n, fe[N], ne[M], he[M]; inline void reset(int sz = 0) { n = sz; m = 0; memset(fe, -1, sizeof(fe)); } inline void insert(int u, int v) { ne[m] = fe[u]; he[m] = v; fe[u] = m++; } }; struct disjoint_set { int r[N]; inline void reset() { for (int i = 0; i < N; ++i) r[i] = i; } inline int find(int i) { return r[i] = (i == r[i] ? i : find(r[i])); } inline void merge(int i, int j) { r[find(i)] = find(j); } }; struct tarjan { int dfn[N], low[N], stk[N], stksz, index; bool instk[N], vst[N]; disjoint_set comp; const glist *g; inline void reset(const glist &graph) { memset(instk, false, sizeof instk); memset(vst, false, sizeof vst); comp.reset(); stksz = index = 0; g = &graph; } void recursive(int u) { int v; dfn[u] = low[u] = index++; vst[u] = true; stk[stksz++] = u; instk[u] = true; for (int e = g->fe[u]; e != -1; e = g->ne[e]) { v = g->he[e]; if (!vst[v] || instk[v]) { if (!vst[v]) recursive(v); low[u] = min(low[u], low[v]); } } if (dfn[u] == low[u]) do { v = stk[--stksz]; instk[v] = false; comp.merge(u, v); } while (u != v); } inline void solve() { for (int i = 0; i < g->n; ++i) if (!vst[i]) recursive(i); } }; int round_count, rule_count; item_t bob_seq[RN]; glist graph; inline int va(int round) { return round << 1; } inline int vb(int round) { return (round << 1) | 1; } inline void read_and_build_graph() { static const int SAME = 0; static const int DIFF = 1; graph.reset(round_count * 2); for (int i = 0; i < rule_count; ++i) { int ra, rb, rule; scanf("%d %d %d", &ra, &rb, &rule); --ra; --rb; if (rule == SAME) { if (bob_seq[ra].x == bob_seq[rb].x) { graph.insert(va(ra), va(rb)); graph.insert(va(rb), va(ra)); graph.insert(vb(ra), vb(rb)); graph.insert(vb(rb), vb(ra)); } else { if (bob_seq[ra] >= bob_seq[rb]) swap(ra, rb); // let b beats a. graph.insert(vb(ra), va(rb)); graph.insert(va(rb), vb(ra)); graph.insert(va(ra), vb(ra)); graph.insert(vb(rb), va(rb)); } } else // if (rule == DIFF) { if (bob_seq[ra].x == bob_seq[rb].x) { graph.insert(va(ra), vb(rb)); graph.insert(vb(rb), va(ra)); graph.insert(vb(ra), va(rb)); graph.insert(va(rb), vb(ra)); } else { if (bob_seq[ra] >= bob_seq[rb]) swap(ra, rb); // let b beats a. graph.insert(va(rb), va(ra)); graph.insert(vb(ra), vb(rb)); } } } } tarjan scc; // Strongly connected comp. inline bool alice_can_win() { scc.reset(graph); scc.solve(); for (int i = 0; i < round_count; ++i) if (scc.comp.find(va(i)) == scc.comp.find(vb(i))) return false; return true; } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int T; scanf("%d", &T); for (int i = 1; i <= T; ++i) { scanf("%d %d", &round_count, &rule_count); for (int j = 0; j < round_count; ++j) scanf("%d", bob_seq + j); read_and_build_graph(); printf("Case #%d: %s\n", i, alice_can_win() ? "yes" : "no"); } 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 | #include <ctime> #include <cstdio> #include <cstdlib> #include <iostream> using namespace std; int main() { freopen("input.txt", "w", stdout); srand(clock()); int T = 100; cout << T << endl << endl; while (T--) { int round = rand() % 20 + 1; int rule = rand() % 20 + 1; cout << round << ' ' << rule << endl; for (int i = 0; i < round; ++i) cout << rand() % 3 + 1 << ' '; cout << endl << endl; for (int i = 0; i < rule; ++i) cout << rand() % round + 1 << ' ' << rand() % round + 1 << ' ' << rand() % 2 << endl; cout << endl << endl; } return 0; } |
