小x的好路-road
Description
小x是一个热爱生活的人。
小x想要进行一次爽快的旅行，借此刺激隔壁国庆只放四天的同学。热爱生活的小x想去体验「抬首仰望，山上苍松茂密，层层叠叠、黛绿如墨，峰峦跌宕如风起云涌，松涛阵阵似万马奔腾。俯瞰山下，其绝美意境如一帘油画尽收眼底。那蜿蜒崎岖的九曲河水，如蛟龙过境迂回向前。」
没错，是「九曲十八弯」！
但焕星的「九曲十八弯」非常大，可以简化为一个具有 nn 个点的完全图，由于小x的旅行路线不同常人，路的方向并不会限制到小x的行动，他只喜欢按照自己的心情来游览这个图。
下面是一些注意事项：
-
小x可以从图中选出若干组不重复的「好路」，可以确定的是两组不同的「好路」不会有重叠的边。
-
由于小x有强迫症，可以确定的是，无论怎么选「好路」，图中的每一条边一定会且只会被选在一个「好路」集合当中，且每个边都会属于一个「好路」集合。
-
每个「好路」有自己的「好值」，「好值」的计算方式为：对于「好路」中的每个顶点，都对「好值」产生贡献，贡献值为「属于该好路的边」中的最大的边权。
即\begin{aligned}Ans={\max(w_i,w_j)}\end{aligned}Ans=max(wi,wj)，其中w_i,w_jwi,wj表示「好路」中的两条边，AnsAns表示该「好路」集合中的一部分「好值」，完整的值为\sum Ans∑Ans。
-
可以确定的是小x圈出来的每组「好路」，都可以看做一个「圈」。
-
奥对，数字99是一个奇数吧？所以这个 nn 也是一个奇数呢！
小x想要知道「九曲十八弯」中，对于所有「好路」，最小的「好值」的和是多少。
Input
第一行给定一个整数 nn ，表示该完全图有 nn 个点。
接下来给定 \frac{n\times(n-1)}{2}2n×(n−1)行，每行有三个整数u,v,wu,v,w，表示 u,vu,v 之间有一条权值为 ww 的路径。
3 \leq n \leq 999，n\mod2\equiv 1，1\leq u,v\leq n,w\leq2\times10^8, u != v3≤n≤999，nmod2≡1，1≤u,v≤n,w≤2×108,u!=v
Output
输出一个整数，代表最小的「好值」的和。
Sample Input 1
5 1 2 1 4 5 1 1 3 1 3 4 2 3 2 4 3 5 5 1 4 6 1 5 4 4 2 2 5 2 4
Sample Output 1
37
Sample Input 2
3 1 2 1 3 1 5 2 3 5
Sample Output 2
15
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define mid (l+r>>1)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int>pii;
typedef vector<int>vi;
struct tri {int a, b, c;};
const int N = 1000 + 10;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
vi edg[N];
ll n,ans;
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
// freopen("in.txt", "r", stdin);
int n;
cin >> n;
for(int i=0;i<n*(n-1)/2;i++)
{
int a,b,c;
cin>>a>>b>>c;
edg[a].push_back(c);
edg[b].push_back(c);
}
for(int i=1;i<=n;i++)
{
sort(edg[i].begin(),edg[i].end());
for(int j=1;j<edg[i].size();j+=2)
ans+=edg[i][j];
}
cout<<ans;
return 0;
}