Portals (USACO Gold 2021 US Open)

这个题初看没有头绪，但仔细画图之后可以找到规律，之后中就挺直观的MST算法。

按图的结构，沿着连通的边走，可以走出一些回到原点的环，比如sample中有三个互不重合的环：

1-2-3-4 (回到1), 5-6-7, 8-9-10

这是因为每个portal是正好连接两个点（出现两次）。

每一个跨越两个环的vertex，通过调整之后，都可以把这两个环连接起来，变成一个环。

所以问题就转化成了，有一系列的环（可以看成是节点），然后有一些代价不同的办法可以把环合并（可以看成是长度不同的边），问把所有环都合并成一个大环的最小代价是什么。这个其实就是问在新的图上面找最小生成树，让所有点之间都连通。

办法就是用union-find把环都找出来，然后用Kruskal一个个合并就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
pair<int,int> c[100005];
int p[100005][4];
int fa[200005];
 
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
int merge(int x, int y) { x = find(x); y = find(y); return x!=y ? (fa[x]=y, true) : false;}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d %d %d", &c[i].first, &p[i][0], &p[i][1], &p[i][2], &p[i][3]);
        c[i].second = i;
    }
    for (int i = 1; i<= 2*n; i++)
        fa[i] = i;
    for (int i = 0; i < n; i++) {
        merge(p[i][0], p[i][1]);
        merge(p[i][2], p[i][3]);
    }
    sort(c,c+n);
 
    // Kruskal to merge "circles"
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int x = c[i].second;
        if (merge(p[x][0], p[x][2])) {
            ans += c[i].first;
        }
    }
    printf("%lld", ans);
 
    return 0;
}