signed

QiShunwang

“诚信为本、客户至上”

全国大学生算法设计与编程挑战赛 (秋季赛)——正式赛 | I: 小x的好路-road

2020/12/30 16:34:15   来源:

小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;
}