@atcoder - Japanese Student Championship 2019 Qualification - E@ Card Collector

古城微笑少年丶 2023-06-01 14:56 8阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

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。

## @solution@ ##

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

我们源点连向每个卡片，容量为 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 code@ ##

#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); }

## @details@ ##

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

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

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11406889.html