CodeForces 1245D Shichikuji and Power Grid

cf题面

解题思路

比赛过程中想了一个贪心——把所有城市按照自建代价排序，排在第一的城市肯定自建，之后依次判断排在后面的城市要自建还是要连接前面的。这么做WA13了（第一次忘开long longWA4）。

赛后看看题解，又参考了之前同样WA13的 Artoriax的代码，大概发现了这种做法的漏洞。假设自建代价是\(c_1，可以构造连边的代价，使得在花费最小的连接方式中，连边应该是1—3—2，我之前那样的做法，1号城市自建以后，判断2号城市要自建还是要连1号城市，再判断3号城市要自建还是要连1号城市或者2号城市。

具体的hack数据如下——

3
1 1
2 2
2 1
1 5 100
1 2 1

说简单点大概就是，1、2、3自建代价是1、5、100，1到2连边代价是5，1到3的连边代价是2，2到3的连边代价是3。最小代价答案是6，我那种方法跑出来是8。

我后来AC的思路大概是：首先假设每个点都自建，那么每个点的代价就是自建代价。然后按照代价排序，用代价最小的点去更新后面那些点，如果能更新用电代价，就把那些点连接到当前点。然后进入下一轮循环，排除上一次代价最小的点，把剩下的点再次按照代价排序，然后用这些点中代价最小的去更新其他的，以此类推。

官方题解还提供了一种更一般的想法：这题其实就是求一个最小生成树，图是这么建的——首先所有点之间连边，边权就是连接代价，然后加一个0号点，所有点向0号点连边，边权是自建代价。这么一想，我AC的思路就是毫无堆优化的、还不如线性直接找最小值的、很蠢的Prim了。

源代码

#include
#include
int n;
struct City{
	int id;
	long long x,y;
	long long cc,kk;
	bool self;
	int fa;
	bool operator < (const City & a)const{
		return cc