[IOI2021] 喷泉公园 题解

考虑将所有放长椅的地方黑白染色，黑色的只连横着的边，白色的只连竖着的边，考虑从上到下，从左到右加入所有边，并尽量保证我们当前的图与所有边都加入的图连通性相同，黑色块上面的边和白色块左面的边一定能加入，只需要考虑两种情况： - 黑色块下面的边  此时三条绿色的边一定已经（可能以等价形式）加入，这条边一定不用加入。 - 白色块右面的边  此时两条绿色的边已经加入，而蓝色的边因为在黑色块上面而一定能加入，于是这条边也不用加入。 所以从实现上来说只需要依次检验所有边是否能加入即可。 ```cpp // #include "parks.h" #include <algorithm> #include <functional> #include <iostream> #include <map> #include <vector> using namespace std; void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b); int construct_roads(vector<int> x, vector<int> y) { int n = x.size(); vector<int> f(n, 0); for (int i = 0; i < n; i++) f[i] = i; function<int(int)> gf = [&](int x) { return f[x] == x ? x : f[x] = gf(f[x]); }; vector<pair<int, int>> v; map<pair<int, int>, int> mp, used; for (int i = 0; i < n; i++) mp[{x[i], y[i]}] = i, v.push_back({x[i], y[i]}); sort(v.begin(), v.end(), [&](auto a, auto b) { if (a.second != b.second) return a.second > b.second; return a.first < b.first; }); vector<int> vu, vv, va, vb; for (auto [x, y] : v) { if (mp.count({x + 2, y})) { int u = mp[{x, y}], v = mp[{x + 2, y}]; if (gf(u) != gf(v)) { int cx = x + 1, cy = y + 1; if (((cx / 2) + (cy / 2)) & 1) cy -= 2; if (used.count({cx, cy})) continue; used[{cx, cy}] = 1; vu.push_back(u), vv.push_back(v), va.push_back(cx), vb.push_back(cy); f[gf(u)] = gf(v); } } if (mp.count({x, y - 2})) { int u = mp[{x, y}], v = mp[{x, y - 2}]; if (gf(u) != gf(v)) { int cx = x + 1, cy = y - 1; if (!(((cx / 2) + (cy / 2)) & 1)) cx -= 2; if (used.count({cx, cy})) continue; used[{cx, cy}] = 1; vu.push_back(u), vv.push_back(v), va.push_back(cx), vb.push_back(cy); f[gf(u)] = gf(v); } } } bool flag = 1; for (int i = 1; i < n; i++) flag &= (gf(i) == gf(0)); if (!flag) return 0; build(vu, vv, va, vb); return 1; } ```