题解 CF1566G 【Four Vertices】
syksykCCC
·
·
题解
给定一张 n 个点的图，初始包含 m 条给定的边。
支持两种操作，共 q 次：
保证任意时刻图中没有重边和自环。
在所有操作前和每次操作后，求出在图中取出两条端点集合不相交的路径的长度之和的最小值。一条路径不能是单独的一个点。保证任意时刻图中边数 \ge 4。
2s, 256MB
----
首先可以发现，在图中任取三条边，最优解都一定不超过它们的距离之和。这个结论是显然的，因为任意三条边至少包含了 $4$ 个端点，那么就必然可以取出一组不相交的路径。
那么我们就已经得知了取三条边的最优方案，接下来只需要考虑取两条边的最优方案。
引理：对于一个点 $u$，如果它的度数 $>3$，那么我们就把与它相连的较大的那些边删去，使得每个点的度数 $\le 3$，这个新图的答案与原图的答案相同。
> 证明：不妨设答案包含了 $(a,b)$ 和 $(c, d)$ 两条边，而 $(a,b)$ 不是与 $a$ 相连的边中前 $3$ 小的，即至少有三条边 $(a, x), (a, y), (a, z)$（$x, y, z$ 互不相同）都小于 $(a, b)$ 的长度，那么根据抽屉原理，$x, y, z$ 中至少有一个点不等于 $c$ 且不等于 $d$，那么我们就可以用这条边替换掉 $(a, b)$ 得到另一组合法的解，与假设矛盾。
根据引理，在这张新图上，我们分两种情况讨论：
1. 答案包括了最小的边：那么我们只需要从小到大依次枚举另一条边，根据抽屉原理，只需要枚举至多 $5$ 次就可以找到一条满足题意的边，所以这部分时间复杂度是 $O(1)$ 的。
2. 答案不包括最小的边：那么我们只需要在第一种情况找到的区间中暴力枚举一个 pair 进行配对即可。因为第一种情况中找到的满足条件的边至多是第 $5$ 小的边，那第二种情况中的两条边都不应当超过第 $4$ 小，也是常数级别的，所以这部分时间复杂度也是 $O(1)$ 的。
于是使用 `set` 等数据结构暴力维护边即可，时间复杂度 $O((m+ q) \log n)$。
```cpp
#include <bits/stdc++.h>
typedef long long ll;
const int N = 1e5 + 5, M = N << 1;
int n, m, q, U[M], V[M], W[M];
std::set<std::pair<int, int>> val[N], vals;
std::map<std::pair<int, int>, int> edges;
int limit(int u) {
if(val[u].size() < 3) return INT_MAX;
return std::next(val[u].begin(), 2)->first;
}
void pop(int u) {
auto it = val[u].begin();
for(unsigned i = 0; i < 3 && i < val[u].size(); i++, it++) {
if(vals.count(*it)) vals.erase(*it);
}
}
void push(int u) {
auto it = val[u].begin();
for(unsigned i = 0; i < 3 && i < val[u].size(); i++, it++) {
if(it->first <= std::min(limit(U[it->second]), limit(V[it->second])))
vals.insert(*it);
}
}
void solve() {
ll res = (ll)vals.begin()->first + std::next(vals.begin(), 1)->first + std::next(vals.begin(), 2)->first;
int maxe = vals.begin()->second;
for(auto it = std::next(vals.begin()); it != vals.end(); it++) {
int id = it->second;
if(U[id] != U[maxe] && U[id] != V[maxe] && V[id] != U[maxe] && V[id] != V[maxe]) {
res = std::min(res, (ll)W[id] + W[maxe]);
for(auto a = std::next(vals.begin()); a != it; a++) {
for(auto b = std::next(a); b != it; b++) {
int x = a->second, y = b->second;
if(U[x] != U[y] && U[x] != V[y] && V[x] != U[y] && V[x] != V[y]) {
res = std::min(res, (ll)W[x] + W[y]);
}
}
}
printf("%lld\n", res); return;
}
}
for(auto a = std::next(vals.begin()); a != vals.end(); a++) {
for(auto b = std::next(a); b != vals.end(); b++) {
int x = a->second, y = b->second;
if(U[x] != U[y] && U[x] != V[y] && V[x] != U[y] && V[x] != V[y]) {
res = std::min(res, (ll)W[x] + W[y]);
}
}
}
printf("%lld\n", res);
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d %d %d", &U[i], &V[i], &W[i]);
if(U[i] > V[i]) std::swap(U[i], V[i]);
val[U[i]].insert({W[i], i}); val[V[i]].insert({W[i], i});
edges[{U[i], V[i]}] = i;
}
for(int i = 1; i <= n; i++) push(i);
solve(); scanf("%d", &q);
while(q--) {
int opt; scanf("%d", &opt);
if(!opt) {
int u, v; scanf("%d %d", &u, &v);
if(u > v) std::swap(u, v);
pop(u); pop(v);
int id = edges[{u, v}];
val[u].erase({W[id], id}); val[v].erase({W[id], id});
edges[{u, v}] = 0;
push(u); push(v);
} else {
m++; scanf("%d %d %d", &U[m], &V[m], &W[m]);
if(U[m] > V[m]) std::swap(U[m], V[m]);
pop(U[m]); pop(V[m]);
val[U[m]].insert({W[m], m}); val[V[m]].insert({W[m], m});
edges[{U[m], V[m]}] = m;
push(U[m]); push(V[m]);
}
solve();
}
return 0;
}
```