g 八分钱

· · 题解

一生有爱何惧风飞沙，gp_hash_table 八分钱小练干哈嘛。

只有小于等于阈值的边可以经过所以考虑 Kruskal 做最小瓶颈。

对边权排序之后从小到大枚举左图的最大阈值，用双指针维护右图阈值最小值。只需要支持 check 左右阈值是否合法。

合法的点对个数等于两边各自能通过的点对个数减去两边都能通过的点对个数。前者可以直接做 Kruskal 的时候用并查集简单预处理，后者考虑对每个点记录信息 (a_u,b_u) 表示点 u 在左图并查集中的根和右图并查集中的根，那么两边都能通过的点对个数是 (a,b) 完全相同的所有集合 S 的 \binom{|S|}{2} 贡献。维护 (a,b) 用哈希表，在双指针移动的时候会合并或者分裂一个连通块，用启发式合并或分裂有 O(n\log n) 次修改 (a_u,b_u)，直接对哈希表修改即可。

复杂度 O(n\log n)。不加任何修改直接使用 gp_hash_table 容易喜提 68pts。

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 2e5 + 10;
int n, m1, m2; LL K, Ans;

struct Edge { int u, v; LL w; } e1[N], e2[N]; LL res1[N], res2[N];

int fa[N], sz[N]; 
int Find(int u) { return (u == fa[u] ? u : fa[u] = Find(fa[u])); }
int trans(Edge* e, LL* res, int m) {
    for (int i = 1; i <= n; i ++) fa[i] = i, sz[i] = 1;
    sort(e + 1, e + 1 + m, [](Edge a, Edge b) { return a.w < b.w; });
    int cnt = 0;
    for (int i = 1; i <= m; i ++) {
        int u = Find(e[i].u), v = Find(e[i].v);
        if (u == v) continue;
        fa[u] = v; res[cnt + 1] = res[cnt] + 1ll * sz[v] * sz[u];
        sz[v] += sz[u]; e[++ cnt] = e[i]; 
    }
    return cnt;
}

vector<int> vec[N], cur[N]; int col[N]; int bel[N];

pair<int, int> info[N]; 

unordered_map<LL, int> hsh; LL curres;
LL get(pair<int, int> a) { return 1ll * a.first * 1145141919 + a.second; }

void undo(int u) {
    for (int x : vec[u]) {
        curres -= (-- hsh[get(info[x])]);
        info[x].first = col[u];
        curres += (hsh[get(info[x])] ++);
    }
}

int main() {
    freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> n >> m1 >> m2 >> K; Ans = 1e18;
    for (int i = 1, u, v, w; i <= m1; i ++) cin >> u >> v >> w, e1[i] = {u, v, w};
    for (int i = 1, u, v, w; i <= m2; i ++) cin >> u >> v >> w, e2[i] = {u, v, w};
    m1 = trans(e1, res1, m1);
    m2 = trans(e2, res2, m2); 

    for (int i = 1; i <= n; i ++) bel[i] = i, cur[i].push_back(i);
    for (int i = 1; i <= m1; i ++) {
        int u = bel[e1[i].u], v = bel[e1[i].v];
        if (cur[u].size() < cur[v].size()) swap(u, v);
        col[i] = v;
        for (int x : cur[v]) vec[i].push_back(x), bel[x] = u, cur[u].push_back(x);
    }
    for (int i = 1; i <= n; i ++) info[i] = {bel[i], i}, hsh[get(info[i])] ++;
    for (int i = 1; i <= m1; i ++) if (res1[i] >= K) Ans = min(Ans, e1[i].w);
    for (int i = 1; i <= m2; i ++) if (res2[i] >= K) Ans = min(Ans, e2[i].w);
    if (!K) { cout << "0\n"; return 0; }
    for (int i = 1; i <= n; i ++) cur[i].clear(), cur[i].push_back(i), bel[i] = i;
    for (int i = 1, j = m1; i <= m2; i ++) if (j) {
        int u = bel[e2[i].u], v = bel[e2[i].v];
        if (cur[u].size() < cur[v].size()) swap(u, v);
        for (int x : cur[v]) {
            curres -= (-- hsh[get(info[x])]);
            info[x].second = u;
            curres += (hsh[get(info[x])] ++);
            cur[u].push_back(x); bel[x] = u;
        }
        while (j) {
            if (res1[j] + res2[i] - curres >= K)
                Ans = min(Ans, e1[j].w + e2[i].w), undo(j --);
            else break;
        }
    } 
    cout << (Ans > (LL)(1e12) ? -1 : Ans) << "\n";
    return 0;
}