传送门

费用流会 T T T,但是没试过 H K HK HK之类的

STD

设武器作用于 x , y x,y x,y两个人(如果 k = 1 k=1 k=1那么令 x = y x=y x=y),收益为 w w w

我们在 x , y x,y x,y之间连一条边权为 w w w的边

那么显然,对于一个 n n n个点的连通块,如果选了 n n n条边

刚好就是一棵树加上一条边刚好成环(基环树)

刚好这个连通块内每个点都可以占据一条边(每个人都有武器)

那么每次都贪心的选择最大边加进连通块

除非这条边连接起来连通块会大于 n n n条边。

证明

设方案 e e e某一次抉择中没有选择最大边 k k k

Ⅰ . Ⅰ. Ⅰ.现在加入最大边 k k k,如果不发生冲突,显然更优秀

Ⅱ . Ⅱ. Ⅱ.如果发生冲突,有两种情况

①最大边 k k k连接的是一个基环树中的点,那么显然断开这棵树的任意一条边填自己更优秀

②最大边 k k k连接的是两个基环树,同上,断开任何一条边会更优秀

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+10;
struct p{
	int x,y,w;
	bool operator < (const p&tmp )	const
	{
		return w>tmp.w;
	}
}e[maxn]; int pre[maxn],n,m,flag[maxn];
int find(int x){ return x==pre[x]?x:pre[x]=find( pre[x] ); }
signed main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++)	pre[i] = i;
	for(int i=1;i<=m;i++)
	{
		int k; cin >> k;
		if( k==1 )	cin >> e[i].x >> e[i].w,e[i].y = e[i].x;
		else	cin >> e[i].x >> e[i].y >> e[i].w;
	}
	sort( e+1,e+1+m );
	int ans = 0;
	for(int i=1;i<=m;i++)
	{
		int fl = find( e[i].x ), fr = find( e[i].y );
		if( fl==fr )//在一个连通块
		{
			if( !flag[fl] )	ans += e[i].w, flag[fl] = 1;	
		}
		else
		{
			if( flag[fl]&&flag[fr] )	continue;//都有环
			else if( !flag[fl]&&!flag[fr] )//都没有环,合并也不会有环 
			{
				ans += e[i].w;
				pre[fl] = fr;
			}	
			else	ans += e[i].w,pre[fl] = fr, flag[fr] = 1;
		} 
	}
	cout << ans;
}