abc270 F – Transportation

题意：

有 \(n\) 个点，你可以花费 \(x_i\) 在点 \(i\) 上建一个机场、花费 \(y_i\) 在点 \(i\) 上建一个港口、或花费 \(w_i\) 建一条边 \(u_i-v_i\)

如果两个点都有机场，那它们俩连通。港口同理。问使图成为连通图的最小花费

\(n\le 2e5\)

思路：

超级源点 \(n+1\) 表示机场，超级源点 \(n+2\) 表示港口，跑最小生成树。然而这俩源点不一定要都连通，咋办？枚举四种方案即可，在各方案中能用的边和对两个超级源点连通性的要求不同

void sol() {
    int n, m; cin >> n >> m;
    vector<array<int, 3> > edges; // w,u,v
    for(int i = 1; i <= n; i++) {
        int w; cin >> w;
        edges.push_back({w, i, n + 1});
    }
    for(int i = 1; i <= n; i++) {
        int w; cin >> w;
        edges.push_back({w, i, n + 2});
    }
    while(m--) {
        int u, v, w; cin >> u >> v >> w;
        edges.push_back({w, u, v});
    }
    
    sort(edges.begin(), edges.end());
    ll ans = 1e18;
    for(int st = 0; st < 4; st++) {
        iota(p, p + N, 0);
        ll res = 0, need = n - 1 + (st & 1) + (st >> 1 & 1);
        for(auto &[w, u, v] : edges) {
            if(v == n + 1 && !(st & 1) || v == n + 2 && !(st >> 1 & 1))
                continue; //不该用这条边
            if(get(u) != get(v))
                p[get(u)] = get(v), res += w, need--;
        }
        if(!need) ans = min(ans, res);
    }
    cout << ans;
}