链接
https://ac.nowcoder.com/acm/contest/9984/F
题意
$n$ 个人，$m$ 个物品，每个物品有一个权值，每个物品可以分给 $1$ 或 $2$ 个人。
物品和人是一对一的关系，请问如何分配能使权值和最大？
思路
将物品当做边，若可分配给两个人，则这两个人为这条边的两个顶点，否则为一个自环。
每条边只能匹配一个点，我们要做的是尽量让更多的点都有一条匹配边，并使边权和最大。
我们可以用并查集维护，在并查集中每个集合相当于一棵树。
两棵树合并仍然是一棵树，总存在一个点没有匹配边。
在一棵树中加入一条边，变为基环树，每个点都有一条匹配边。
基环树与树合并仍然是基环树。
因此可以按照边权从大到小考虑：
- 两个点在一个集合：
- 该集合为树，加入一条边，每个点都能匹配一条边，变为基环树；
- 该集合为基环树，无法加入边，因为每个点都能匹配一条边。
- 两个点不在一个集合：
- 两个集合都为树，加入一条边仍然为树；
- 一个集合为树，一个集合为基环树，加入一条边，每个点都能匹配一条边，合并后为基环树；
- 两个集合都为基环树，无法加入边，因为每个点都能匹配一条边。
按照上述策略，只要能够加入边，那么这条边必被选。
设这条边权较大的边为 $e$，两个顶点为 $u,v$，假设按照上述策略，在能够加入边 $e$ 的情况下，没有加入边 $e$：
- $u$ 所在集合为树，$v$ 所在集合为树，加入边 $e$ 能够多一个点匹配一条边，边权和变大；
- $u$ 所在集合为树，$v$ 所在集合为基环树，加入边 $e$ 能够多一个点匹配一条边，边权和变大；
- $u$ 所在集合为基环树，$v$ 所在集合为基环树，从环中去掉边权最小的边，加入边 $e$，仍然为基环树，边权和变大。
因此，只要能够加入边，那么这条边必被选。
代码
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=1e5+5;
int n,m,fa[N];
LL res;
bool st[N];
struct E {
int u,v,w;
E() {}
E(int u,int v,int w):u(u),v(v),w(w) {}
bool operator < (const E &T) const {
return w>T.w;
}
};
vector<E> e;
int find(int x) {
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y,int v) {
int tx=find(x),ty=find(y);
if(st[tx]&&st[ty]) return;
res+=v;
if(st[tx]&&!st[ty]) fa[ty]=tx;
else if(!st[tx]&&st[ty]) fa[tx]=ty;
else if(tx==ty) st[tx]=true;
else fa[tx]=ty;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;i++) {
int k,u,v,w;
cin>>k>>u;
if(k==2) cin>>v;
cin>>w;
if(k==1) e.EB(u,u,w);
else e.EB(u,v,w);
}
sort(ALL(e));
for(int i=1;i<=n;i++) fa[i]=i;
for(auto x:e) merge(x.u,x.v,x.w);
cout<<res<<'\n';
return 0;
}
|