@atcoder - Japanese Student Championship 2019 Qualification - [email protected] Card Collector


@[email protected]

N 个卡片放在 H*W 的方格图上,第 i 张卡片的权值为 Ai,放在 (Ri, Ci)。一个位置可以放置多张卡片。

你可以在每行捡起最多一张卡片,然后在每列捡起最多一张卡片。

求捡起的卡片权值最大和。

Constraints
所有值都是整数。
1≤N≤10^5, 1≤H,W≤10^5, 1≤Ai≤10^5, 1≤Ri≤H, 1≤Ci≤W。

Input
输入的形式如下:
N H W
R1 C1 A1
R2 C2 A2
?
?
RN CN AN

Output
输出可能的最大权和。

Sample Input
6 2 2
2 2 2
1 1 8
1 1 5
1 2 9
1 2 7
2 1 4
Sample Output
28

样例解释如下:
从第一行捡起第四张卡 A4。
从第二行捡起第六张卡 A6。
从第三行捡起第二张卡 A2。
从第四行捡起第五张卡 A5。
最后权值和 = A4 + A6 + A2 + A5 = 9 + 7 + 4 + 8 = 28。

@[email protected]

看到这个题就知道它一定是个网络流。

我们源点连向每个卡片,容量为 1,费用为权值;卡片连向它所在的行与列,容量为 1,费用为 0;每行每列向汇点连边,容量为 1,费用为 0。
这样建图跑出来的最大费用流就是答案。

观察这个建图,思考发现它总是先沿着卡片权值最大的路径尝试增广,且它的增广过程是不会撤回的(即以前增广过的卡片不会在某一次增广中被删掉)。
所以:我们可以考虑按权值从大到小加入每张卡片,判断每次加入的卡片是否能与之前的卡片共存。

考虑我们建出来的图实际上一个二分图,我们可以使用 hall 定理判定每次加入卡片后,图中是否依然存在完美匹配。
回想 hall 定理的内容:一个点集 S 的 size <= 它邻集 T 的 size,也可以写作 |T| - |S| >= 0。我们这里的点集的邻集就代表它们所在的行列集合。

我们尝试去找不满足 hall 定理的情况。
假如仅存在单独一个点,则 |T| - |S| = 1。如果加入一个与它不在同一行或同列的点,此时 |T| - |S| 会变大,与我们目的相悖;加入一个与它在同一行或同一列的点时,|T| - |S| 不变,但之后加入的点更有可能使得 |T| - |S| 变小,所以加入这个点更有可能不满足 hall 定理。
于是:我们通过找这个点集同一行同一列的所有点不断扩大点集,到无法扩大时再判断此时的 |T| - |S| 是否满足 hall 定理。

具体到实现,我们可以对行与列建并查集,并查集内统计这个行列集合含多少行多少列(即上文的 |T|)与这些行列上有多少卡片(即上文的 |S|)。
每次加入一张卡片就把它所在的行列集合通过并查集合并,同时维护一下。当然要在加入之前判断是否合法(即是否加入完这张卡片,它所在的集合会出现 |T| - |S| < 0)。

@accepted [email protected]

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
struct node{
    int R, C, A;
    friend bool operator < (node a, node b) {
        return a.A < b.A;
    }
}nd[MAXN + 5];
int fa[2*MAXN + 5], key[2*MAXN + 5], siz[2*MAXN + 5];
int find(int x) {
    return fa[x] = (fa[x] == x ? x : find(fa[x]));
}
int N, H, W;
int main() {
    long long ans = 0;
    scanf("%d%d%d", &N, &H, &W);
    for(int i=1;i<=H;i++) fa[i] = i, siz[i] = 1, key[i] = 0;
    for(int i=1;i<=W;i++) fa[i + H] = i + H, siz[i + H] = 1, key[i + H] = 0;
    for(int i=1;i<=N;i++)
        scanf("%d%d%d", &nd[i].R, &nd[i].C, &nd[i].A);
    sort(nd + 1, nd + N + 1);
    for(int i=N;i>=1;i--) {
        int fx = find(nd[i].R), fy = find(nd[i].C + H);
        if( fx == fy ) {
            if( siz[fx] >= key[fx] + 1 ) {
                key[fx]++;
                ans += nd[i].A;
            }
        }
        else {
            if( siz[fx] + siz[fy] >= key[fx] + key[fy] + 1 ) {
                siz[fx] += siz[fy], key[fx] += key[fy] + 1, fa[fy] = fx;
                ans += nd[i].A;
            }
        }
    }
    printf("%lld\n", ans);
}

@[email protected]

被老师莫名其妙拉去打这种奇怪的比赛。。。

在我印象里,现在 hall 定理的题还是算比较少的吧,记下来记下来。

相关文章
相关标签/搜索