题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=4883
题意:给出一个$N \times M$的棋盘,每个格子有权值。你需要每一行选中一个格子,每一列也选中一个格子(一个格子不能同时被行选中和被列选中),求这些格子权值和的最小值,$2 \leq N,M \leq 10^5 , N \times M \leq 10^5$
考虑将行与列拆成点,格子的权值变为连接其对应行与列对应节点的边,我们的问题也就是需要找到一个边集,使得每一条边都在只匹配其端点中的一个的情况下匹配到每一个点,并且边权之和最小。考虑如何找“每一条边都在只匹配其端点中的一个的情况下匹配到每一个点”的边集。我们发现一棵有$N$个节点的树可以匹配$N - 1$个点,那么我们再在树上加一条边,构成基环树,就能够满足条件了。如果我们将边变为有向边,方向向其匹配的那个点,那么满足条件的基环树就是基环外向树。所以我们的目标就是找到这个图中的最小生成基环森林,使用类似$Kruskal$的方法可以实现。
具体的实现方式在并查集上有不同。我们维护某个集合中是否有环。如果某条边对应的两个端点在同一并查集中,如果没有环则设为有环并加上边权,否则无法合并;合并时两个有环的并查集无法合并,否则合并这两个集合,并且继承有无环的状态。
#include<bits/stdc++.h> #define ll long long #define MAXN 100010 using namespace std; inline ll read(){ ll a = ; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return a; } struct Edge{ ll start , end , w; }Ed[MAXN]; ll fa[MAXN] , N , M; bool vis[MAXN]; bool cmp(Edge a , Edge b){ return a.w < b.w; } ll find(ll x){ return fa[x] == x ? x : (fa[x] = find(fa[x])); } int main(){ ll ans = ; N = read(); M = read(); ; i <= N ; i++) ; j <= M ; j++){ Ed[(i - ) * M + j].start = i; Ed[(i - ) * M + j].end = j + N; Ed[(i - ) * M + j].w = read(); } sort(Ed + , Ed + N * M + , cmp); ; i <= N + M ; i++){ fa[i] = i; vis[i] = ; } ; i <= N * M ; i++){ ll p = find(Ed[i].start) , q = find(Ed[i].end); if(p != q && !(vis[p] && vis[q])){ fa[q] = p; ans += Ed[i].w; vis[p] |= vis[q]; } else if(!vis[p]){ vis[p] = ; ans += Ed[i].w; } } cout << ans; ; }