宿命的P.S.S

题目描述

1.背景描述Background
P.S.S:“我来自哪里？”
WH:“你来自一个图。”
P.S.S:“我是谁？”
WH:“你是最小生成树。”
P.S.S:“我又要到哪里去？”
WH:“你要成为一个最小完全图（边权之和最小的完全图）。”
P.S.S:“为……为什么啊？”
WH:“这是你的宿命！因为你无聊！！！P.S.S！”
2.问题描述Description
最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因，把这件事交给了你。
PS: 可以保证，这个最小生成树对于最后求出的完全图是唯一的。
7.时间限制Time Limitation
每个测试点1s。
8.数据规模：
Test1-Test10 n<60
Test11-Test25 n<20000
注释Hint:
对于样例1，我们只需在1-3间加入一条边权为8的边即可得到最小完全图。其权和是4+7+8=19。对于样例2，我们在2-3间加入一条边权为2的边，在2-4和3-4间加入边权为3的边即可得到最小完全图，其权和是：1+1+2+2+3+3=12。
感谢吴豪牛对比赛的支持!!!

输入格式

输入的第一行是一个整数n，表示生成树的节点数。
接下来有n-1行，每行有三个正整数，依次表示每条边的端点编号和边权。
（顶点的边号在1-n之间，边权<maxint）

输出格式

一个整数ans，表示以该树为最小生成树的最小完全图的边权之和。

本题乃逆向思维的经典题目啊。

首先O(n^2)的算法肯定是不能过的。

用kruskal算法的逆算法。

经典经典

 1 #include<iostream>
 2 #include<fstream>
 3 #define fin cin
 4 using namespace std;
 5 //ifstream fin("cin.in");
 6 
 7 long long n,ans=0;
 8 long long f[20005],tot[20005];
 9 struct{long long u,v,w;}edg[20005];
10 
11 void Quick(long long l,long long r){
12      if(l>=r) return ;
13      long long i=l,j=r,mid=edg[(l+r)>>1].w;
14      while(i<=j)
15      {
16        while(edg[i].w<mid) i++;
17        while(edg[j].w>mid) j--;
18        if(i<=j)
19        {
20          swap(edg[i].u,edg[j].u);
21          swap(edg[i].v,edg[j].v);
22          swap(edg[i].w,edg[j].w);
23          i++;j--;
24                }   
25                 }
26      Quick(l,j);
27      Quick(i,r);
28      }
29 
30 long long Find(long long v){
31      if(f[v]==v) return v;
32      f[v]=Find(f[v]);
33      return f[v];
34      }
35 
36 int main()
37 {
38     fin>>n;
39     
40     for(long long i=1;i<n;++i)
41     fin>>edg[i].u>>edg[i].v>>edg[i].w;
42     for(long long i=1;i<=n;++i)
43     f[i]=i,tot[i]=1;
44     
45     Quick(1,n-1);
46     
47     for(long long i=1;i<n;++i)
48     {
49       long long fy=Find(edg[i].u);
50       long long fx=Find(edg[i].v);
51       ans+=edg[i].w+(tot[fy]*tot[fx]-1)*(edg[i].w+1);
52       f[fx]=fy;
53       tot[fy]+=tot[fx];
54              }
55     cout<<ans<<endl;
56    // system("pause");
57     return 0;
58     
59     }