CodeForces 875F Royal Questions

十月 19, 2020 2854

题意简述

有 x 个王子 y 个公主，每一个公主喜欢其中两个王子，还有 一个美丽度。你需要将王子和公主配对，使得配对的每一个公主都和自己喜欢的王子配对，并且配对的公主美丽度之和最大。

注意并不必要让所有的王子公主都得到配对。

解题思路

考虑把每个公主抽象为一条无向边，连接两个王子，边权为美丽度。（怎么想出来的我也不知道）

那么问题就转化为了求一个最大生成基环树。因为一个生成基环树有 n 个点 n 条边，正好满足一个公主配对一个王子。

Kruskal 小改一下就行了。

代码细节

具体地，考虑维护一个单环并查集， u_x 表示 x 的祖先（可用路径压缩）， c_x 表示 x 所在连通块是否有环。

合并 (x, y) 的时候判断一下：

  • 如果 u_x = u_y 即马上要连环，而且 c_x = 0 即 这个连通块还没有环，就可以连一下，把 c_x 设为 1
  • 如果 u_x 不等于 u_y 即这个连的不是环，就判断一下 u_x 和 u_y 两个连通块里有没有环，如果同时有环的话就不能连，不然就可以连

更多细节见代码（其实也没什么细节了）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 200000 + 10;

struct REdge {
    int u, v, w;
    REdge(int _u = 0, int _v = 0, int _w = 0) {
        u = _u; v = _v; w = _w;
    }
    bool operator < (const REdge &th) const {
        return w > th.w;
    }
} es[MAXN];

struct DSU {
    int u[MAXN];
    bool circ[MAXN];

    DSU() { memset(u, 0, sizeof u); memset(circ, 0, sizeof circ); }
    int Find(int x) {
        return !u[x] ? x : u[x] = Find(u[x]);
    }
    bool Merge(int x, int y) {
        x = Find(x), y = Find(y);
        if (x == y) {
            if (!circ[x]) {
                circ[x] = true; return true;
            } else return false;
        }
        if (circ[x] && circ[y]) return false;
        u[x] = y; circ[y] |= circ[x]; return true;
    }
} U;

int n, m;

long long int Kruskal() {
    std::sort(es + 1, es + 1 + m);
    int cnt = 0; long long int ans = 0;
    for (int i = 1; i <= m; ++i) {
        if (U.Merge(es[i].u, es[i].v)) {
            ans += es[i].w; ++cnt;
        }
        if (cnt == n) break;
    }
    return ans;
}

int main() {
    n = read(); m = read();
    for (int i = 1; i <= m; ++i) {
        // 将每个公主抽象为一条边，连接两个王子
        int u = read(); int v = read(); int w = read();
        es[i] = REdge(u, v, w);   
    } 
    // 跑最大生成基环树
    printf("%lld\n", Kruskal());
    return 0;
}