第二届全国大学生算法设计与编程挑战赛-I-小x的好路-road

深藏阁楼爱情的钟 2022-12-21 13:54 174阅读 0赞

# Description #

小x是一个热爱生活的人。

小x想要进行一次爽快的旅行，借此刺激隔壁国庆只放四天的同学。热爱生活的小x想去体验「抬首仰望，山上苍松茂密，层层叠叠、黛绿如墨，峰峦跌宕如风起云涌，松涛阵阵似万马奔腾。俯瞰山下，其绝美意境如一帘油画尽收眼底。那蜿蜒崎岖的九曲河水，如蛟龙过境迂回向前。」

没错，是「九曲十八弯」！

但焕星的「九曲十八弯」非常大，可以简化为一个具有 n 个点的完全图，由于小x的旅行路线不同常人，路的方向并不会限制到小x的行动，他只喜欢按照自己的心情来游览这个图。

下面是一些注意事项：

*  小x可以从图中选出若干组不重复的「好路」，可以确定的是两组不同的「好路」不会有重叠的边。
 *  由于小x有强迫症，可以确定的是，无论怎么选「好路」，图中的每一条边一定会且只会被选在一个「好路」集合当中，且每个边都会属于一个「好路」集合。
 *  每个「好路」有自己的「好值」，「好值」的计算方式为：对于「好路」中的每个顶点，都对「好值」产生贡献，贡献值为「属于该好路的边」中的最大的边权。

![在这里插入图片描述][20201116150041811.png_pic_center]

*  可以确定的是小x圈出来的每组「好路」，都可以看做一个「圈」。
 *  奥对，数字99是一个奇数吧？所以这个n也是一个奇数呢！

小x想要知道「九曲十八弯」中，对于所有「好路」，最小的「好值」的和是多少。

# Input #

![在这里插入图片描述][20201116150119993.png_pic_center]

# 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 #

# Sample Input 2 #

3  
1 2 1  
3 1 5  
2 3 5

# Sample Output 2 #

# 题解 #

每个顶点都对结果有贡献，那么就分别考虑每个顶点——对于每个顶点来说，假设其相连的边按从大到小的权值排序后分别为e1,e2,e3,…，最优的方案就是e1与e2组合，e3与e4组合…这样，该顶点对结果的贡献值为e1+e3+e5+…。处理所有顶点，最终结果即为最终解。可以证明该贪心算法的正确性。

# 代码 #

#include <iostream>
    #include <vector>
    #include <algorithm> 
    using namespace std;
    int main() { 
    	int n;
    	cin>>n;
    	vector<long long> ve[n];
    	for(int i=0; i<((n-1)*(n))/2; i++) { 
    		int u,v,w;
    		cin>>u>>v>>w;
    		u--;
    		v--;
    		ve[u].push_back(w);
    		ve[v].push_back(w);
    	}
    	long long sum=0;
    	for(int i=0; i<n; i++) { 
    		sort(ve[i].begin(),ve[i].end());
    		for(int j=1; j<n; j+=2) { 
    			sum+=ve[i][j];
    		}
    	}
    	cout<<sum;
    	return 0;
    }

[20201116150041811.png_pic_center]: /images/20221120/912610e95aa840719d81bcd84f1e8bc3.png
[20201116150119993.png_pic_center]: /images/20221120/0e7c9a056afe4a40aabdeff67551a798.png