CF875F Royal Questions

建模神仙题。

Link

刚开始拿到题目，发现这就是一个二分图最大权匹配板题。然而 \(n,m\leq 2\times 10^5\)，显然不可做。

我们从贪心的角度去考虑这个问题。如果我们贪心地从大到小匹配夫妻，那么就会出现一个问题：如何判定合不合法？

很容易想到，一个公主选了其中一个王子，那么另一个就不能再被她选了。那么我们不妨把她所喜欢的两个王子中间连一条边，表示一种「互斥」的关系。现在公主就被转化成了一条边，王子则变成一个点。

合法的情况显然当所有的点出度都为 \(1\)。也就是说，应当是一个基环树森林。从叶子节点开始，每个节点和它更靠近环的一条边作为一对夫妻，环上的则按照顺时针或逆时针方向结为夫妻。

然而实际上我们并不需要让每个点的度数都为 \(1\)。考虑一棵树的情况，我们完全可以让根节点单独拎出来，剩下的全部都结为夫妻。也就是说，树森林也是合法的。

只需要用并查集维护即可。具体地，我们多维护一个 \(tag\) 表示当前是树/基环树。树和基环树显然是可以合并成基环树的。如果当前 \(u,v\) 在同一个集合里，并且目前形成的是树，那么我们也可以把它变成基环树。

时间复杂度 \(O(n\log n)\)，其实可以做到 \(O(n\alpha(n))\)。

struct Edge
{
    int u, v, w;
}e[MAXM << 1];

int n, m, cnt, ans;
int fa[MAXN];
bool tag[MAXN];

void add_edge(int u, int v, int w)
{
    e[++cnt] = {u, v, w};
}

int find(int x)
{
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}

signed main()
{
    read(n, m);
    for(int i = 1; i <= n; i++) fa[i] = i, tag[i] = 1;
    for(int i = 1; i <= m; i++)
    {
        int a, b, w;
        read(a, b, w);
        add_edge(a, b, w);
    }
    sort(e + 1, e + 1 + cnt, [](Edge A, Edge B){return A.w > B.w;});
    for(int i = 1; i <= cnt; i++)
    {
		int u = find(e[i].u), v = find(e[i].v);
        if(u != v && (tag[u] | tag[v])) fa[u] = v, ans += e[i].w, tag[v] = tag[u] & tag[v];
        if(u == v && tag[u]) tag[u] = 0, ans += e[i].w;
	}
    printf("%d\n", ans);
    return 0;
}