題目
完全圖：
引用一個寫的不錯的題解
其實此題就是變形的最小生成樹
每兩個點之間都存在且僅存在一條邊
由于題中給出的是一個完全圖的最小生成樹的樹邊见擦，對于題中給出每一條邊（u晓猛，v），顯然u和v并不連通铣耘。因為原圖為一個完全圖渊涝，那么完全圖的部分點構(gòu)成的圖也為完全圖。假設(shè)u所在完全圖G1中偷溺，G1中有點n1個，v所在完全圖G2中钱贯，G2中有點n2個挫掏，那么，連接邊（u秩命，v）尉共，并且使得u，v兩個完全圖合為一個完全圖還需要連n1n2-1條邊弃锐，邊權(quán)至少要大于邊（u袄友，v）的權(quán)值，要讓完全圖邊權(quán)總和最小霹菊，即讓這n1n2-1條邊的邊權(quán)為邊（u杠河，v）的邊權(quán)加1即可。
但我們又想到一個問題浇辜，怎么保證這樣生成的完全圖的最小生成樹和原題相同？顯然唾戚，先連接邊權(quán)大的邊柳洋，在連接邊權(quán)小的邊，前面連接的邊權(quán)較大的邊會被后面邊權(quán)小的邊連接時補全圖為完全圖時的邊替代叹坦。文字難以理解熊镣，這里講一個簡單的例子。
3
2 3 7
1 2 4
沒錯，就是樣例绪囱，只是將第一條邊和第二條邊的位置互換测蹲，處理時我們從前往后處理。第一條邊權(quán)值為7鬼吵，連接后不需要補邊（已經(jīng)為完全圖）扣甲，第二條邊權(quán)值為4，需要補邊（1,3）才能使原圖變?yōu)橥耆珗D齿椅，權(quán)值為當前邊權(quán)值加1琉挖，即為5，顯然涣脚，在最小生成樹中示辈，邊（2,3）會被邊（1,3）替代，即操作不合法遣蚀。
但是矾麻，如果我們保證前面的邊的邊權(quán)小于等于后面的邊權(quán)，那么芭梯，求出的完全圖的正確性就有保障了险耀。
根據(jù)上面所講，這題和kruskal是不是很像粥帚？一開始將邊以邊權(quán)從小到大排序胰耗，記錄每個點所在集合中的元素個數(shù)為d[i]，對于每一條邊（u芒涡，v）柴灯，邊權(quán)為val，ans+=val+（val+1）（d[root[u]]d[root[v]]-1）其中root[i]表示i所在集合的代表元素费尽。最后輸出ans即可赠群。
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int x,y,z;
}edge[20005];
int n,fa[20005];
long long ans,d[20005];
bool cmp(node a,node b)
{
if (a.z<b.z) return true;
else return false;
}
int find(int x)
{
if (fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
int main()
scanf("%d",&n);
for (int i=1; i<n; i++)
scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
sort(edge+1,edge+n,cmp);
for (int i=1; i<=n; i++)
{
fa[i]=i;
d[i]=1;
}
for (int i=1; i<n; i++)
{
int rx=find(edge[i].x);
int ry=find(edge[i].y);
ans+=edge[i].z+(edge[i].z+1)*(d[rx]*d[ry]-1);
d[ry]+=d[rx];
fa[rx]=ry;
}
printf("%lld\n",ans); return 0;
}