[IOI2021] 喷泉公园 题解
swiftc
2023-03-20 22:45:48
考虑将所有放长椅的地方黑白染色,黑色的只连横着的边,白色的只连竖着的边,考虑从上到下,从左到右加入所有边,并尽量保证我们当前的图与所有边都加入的图连通性相同,黑色块上面的边和白色块左面的边一定能加入,只需要考虑两种情况:
- 黑色块下面的边
![](https://cdn.luogu.com.cn/upload/image_hosting/8fzpc7kh.png)
此时三条绿色的边一定已经(可能以等价形式)加入,这条边一定不用加入。
- 白色块右面的边
![](https://cdn.luogu.com.cn/upload/image_hosting/2kp1r9fm.png)
此时两条绿色的边已经加入,而蓝色的边因为在黑色块上面而一定能加入,于是这条边也不用加入。
所以从实现上来说只需要依次检验所有边是否能加入即可。
```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;
}
```