ABC-383-E - Sum of Max Matching · znzryb

## 思路讲解

[参考洛谷题解](https://www.luogu.com.cn/article/wqpqn6sc)

在kruskal的过程中求解这个问题，然后如果发现合并的复杂度太高，看看用数量代替set的合并可不可以？

然后记得结构体的全部数组要初始化

## AC代码

[https://atcoder.jp/contests/abc383/submissions/62364335](https://atcoder.jp/contests/abc383/submissions/62364335)

```cpp
// Problem: E - Sum of Max Matching
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_e
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define debug(x) cerr<<x<<'\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(2e5)+10,MAXval=static_cast<ll>(5e18)+3;

ll N,M,K;
vector<pll> G[MAXN];
struct Triple{
	ll u,v,w;
};
struct cmp{
	bool operator()(const Triple &a,const Triple &b)const{
		return a.w>b.w;
	}
};
priority_queue<Triple,vector<Triple>,cmp> pq;

struct FA{
	                 // 初始每个点的未匹配点数量
	ll fa[MAXN],size,numa[MAXN],numb[MAXN];
	inline void init(ll range){
		size=range;
		FOR(i,1,size){	// 初始化并查集
			fa[i]=i;
			numa[i]=0;
			numb[i]=0;
		}
	}
	ll find(ll x){
		if(fa[x]==x) return x;
		return fa[x]=find(fa[x]);
	}
	inline void merge(ll a,ll b){
		ll faA=find(a),faB=find(b);
		fa[faA]=faB;
		// 将a合并入b
		numa[faB]+=numa[faA];
		numb[faB]+=numb[faA];
		// debug(numa[faB]);
		// debug(numb[faB]);
	}
	inline ll match(ll a,ll b){
		ll faA=find(a),faB=find(b);
		ll aOption=min(numa[faA],numb[faB]),bOption=min(numb[faA],numa[faB]);
		numa[faA]-=aOption;
		numb[faB]-=aOption;
		numb[faA]-=bOption;
		numa[faB]-=bOption;
		return aOption+bOption;
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M>>K;
	FA fa;
	fa.init(N); 
	FOR(i, 1, M){
		ll u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
		pq.push((Triple){u,v,w});
	}
	FOR(i,1,K){
		ll a;
		cin>>a;
		fa.numa[a]+=1;
	}
	FOR(i,1,K){
		ll b;
		cin>>b;
		fa.numb[b]+=1;
	}
	// FOR(i,1,N){
		// cerr<<fa.numa[i]<<' ';
	// }
	// cerr<<'\n';
	// FOR(i,1,N){
		// cerr<<fa.numb[i]<<' ';
	// }
	// cerr<<'\n';
	ll ans=0;
	// kruskal（最小生成树+无向图判环）
	while(!pq.empty()){
		ll u=pq.top().u,v=pq.top().v,w=pq.top().w;
		pq.pop();
		if(fa.find(u)!=fa.find(v)){
			ans+=w*fa.match(u,v);
			// cerr<<u<<' '<<v<<' '<<w<<' '<<ans<<' '<<'\n';
			fa.merge(u,v);
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*

*/
```

## 心路历程（WA，TLE，MLE……）

[https://atcoder.jp/contests/abc383/submissions/62364233](https://atcoder.jp/contests/abc383/submissions/62364233)

类的数组记得要init（）

```cpp
	inline void init(ll range){
		size=range;
		FOR(i,1,size){	// 初始化并查集
			fa[i]=i;
			numa[i]=0;
			numb[i]=0;
		}
	}
```