gym102392J Graph and Cycles

https://codeforces.com/gym/102392/problem/J

训练的时候在想最小生成树卧槽。。。甚至发现复杂度挺对的，然而byf说不太对就没写了，最近训练赛也比较浮躁

问题可以转化为，每次相邻的两条边都会经过一个点，而且由于是奇数个点的完全图，一个点有n-1条边，所以无论怎么划分，每个点的两条边，两条边会这样被划分金一个环，那么所有环的值，就是考虑所有点的边的划分情况，

那么贪心的有每个点按照边从小到大排序，相邻大小分在一个环，这样是最优的。

#include<bits/stdc++.h>
#define maxl 1010
using namespace std;

int n;
long long ans=0;
vector <int> e[maxl];

inline void prework()
{
	scanf("%d",&n);
	int u,v,w,l=n*(n-1)/2;
	for(int i=1;i<=l;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		e[u].push_back(w);
		e[v].push_back(w);
	}
}

inline void mainwork()
{
	for(int i=1;i<=n;i++)
	{
		sort(e[i].begin(),e[i].end());
		int l=e[i].size();
		for(int j=0;j<l;j+=2)
			ans+=max(e[i][j],e[i][j+1]);
	}
}

inline void print()
{
	printf("%lld",ans);
}

int main()
{
	prework();
	mainwork();
	print();
	return 0;
}