题解：AT_jsc2019_qual_e Card Collector

图论建模还是太神仙了。

首先思考一下题目给的条件，每行只选一个，接着每列只选一个，由于这种唯一对应的性质，很容易让人想到二分图匹配，但数据范围并不允许我们这样做。

但这给我们一个图论建模的思路。考虑一张卡片在

(x,y)

上，权值为

v

，我们可以看作在点

x

和点

y+r

之间连了一条权值为

v

的边。为了区分第一步操作和第二步操作，有一个 trick 是让边有方向。钦定如果是在第一步操作中（即从每一行中选取卡片），让边的方向为

x

到

y+r

，否则让边的方向为

y+r

到

x

。

接下来研究一下图的性质。根据题目限制我们可以发现一个点最多只能向外连一条边（因为若不保证这一点，则根据钦定的变的定义，会出现一行选取多个点或一列选取多个点的情况），即出度为

1

，这显然就是内向基环树森林。

但有向边不好处理，所以接下来一步比较奇妙的处理就是让有向边变成无向边。那么为什么可以直接转换？我们只要保证一个点在有向图中出度为

1

即可保证方案合法，那么再边变为无向后的新图中只要保证每一个联通块都是树或基环树。

稍微证明一下：如果是树，一种构造方法是让边的方向一致朝下。如果是基环树，只要让环部分的边转一圈回到起始点，其他边向环的方向指即可。如下图所示：

那么唯一的问题在于如何求出选哪些边是的它们组成一颗颗树或者基环树。其实只用在 Kruskal 求最大生成树的过程中加一个标记数组标记该连通块是基环数还是树即可。遵循以下规则：

如果联通块内部点相连接，那么该联通块一定是一棵树，连完后它成为一颗基环树。
如果是两个联通块相连，那么一定不能是两个基环树，假如两个联通块有一个是基环树，那么连完后整体是基环树，反之是树。

可自行证明一下这样做一定是符合定义的，并不难证。

代码如下:

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct A {
    int x, y, v;
    bool operator<(const A &h) const { return v < h.v; }
} e[5000000];
int tmp;
int t[5000000];
bool cmp(A x, A y) { return x.v > y.v; }
int find(int x) {
    if (t[x] == x) {
        return x;
    }
    return t[x] = find(t[x]);
}
int bz[5000000];
signed main() {
    int n, r, c;
    scanf("%lld%lld%lld", &n, &r, &c);
    for (int i = 1; i <= n; i++) {
        int x, y, v;
        scanf("%lld%lld%lld", &x, &y, &v);
        e[++tmp] = { x, y + r, v };
    }
    sort(e + 1, e + 1 + tmp, cmp);
    for (int i = 1; i <= r + c; i++) {
        t[i] = i;
    }
    int ans = 0;
    for (int i = 1; i <= tmp; i++) {
        int fx = find(e[i].x), fy = find(e[i].y);
        if (fx == fy) {
            if (!bz[fx]) {
                ans += e[i].v;
                bz[fx] = 1;
            }
            continue;
        }
        if (!bz[fx] || !bz[fy]) {
            t[fx] = fy;
            bz[fy] =bz[fx]=bz[fy]|bz[fx];
            ans += e[i].v;
        }
    }
    printf("%lld", ans);
}

题解：AT_jsc2019_qual_e Card Collector

文章操作

相关推荐

评论

题解：AT_jsc2019_qual_e Card Collector