时间限制: 

10000ms

 

单个测试点时间限制: 

1000ms

 

内存限制: 

512000kB

描述

华北电力大学可以抽象为一张有n个点m条边的无向图.

 

现在所有的边都断了. 修复每条边都有个不同的代价w_i.

 

求让所有点都能互相到达的最小代价和.

输入

第一行两个正整数 n, m 表示顶点数和边数

接下来m行每行三个正整数 u v w 表示一条边 (u和v是边的端点, w是边权)

输出

输出一行一个正整数表示答案

样例输入

2 21 2 22 1 3

样例输出

2

提示

n ≤ 10^5, m ≤ 3*10^5, w ≤ 10^4 保证有解

来源

laekov

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int MAXN=1200001; 8 const int maxn=0x3f; 9 void read(int &n)10 {11     char c=‘+‘;int x=0;bool flag=0;12     while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}13     while(c>=‘0‘&&c<=‘9‘)14     x=(x<<1)+(x<<3)+c-48,c=getchar();15     flag==1?n=-x:n=x;16 }17 struct node18 {19     int u,v,w,nxt;20 }edge[MAXN];21 int head[MAXN];22 int num=1;23 int add_edge(int x,int y,int z)24 {25     edge[num].u=x;26     edge[num].v=y;27     edge[num].w=z;28     edge[num].nxt=head[x];29     head[x]=num++;30 }31 int n,m;32 int vis[MAXN];33 int dis[MAXN];34 struct pr35 {36     int p,v;37     pr()38     {p=v=0;}39     pr(int a,int b)40     {p=a;v=b;}41     bool operator<(const pr&a)const 42     {return v>a.v;}43 }inc;44 void prime()45 {46     //vis[1]=1;47     priority_queue<pr>q;48     memset(dis,maxn,sizeof(dis));49     dis[1]=0;50     q.push(pr(1,0));51     int ans=0;52 //    for(int i=head[1];i!=-1;i=edge[i].nxt)53 //        q.push(pr(edge[i].v,edge[i].w));54     55     for(int k=1;k<=n;k++)56     {57         int pos;58         while(vis[q.top().p]&&q.size()>=0)59             q.pop();60     61         pos=q.top().p;62         vis[pos]=1;63         ans+=dis[pos];64         for(int i=head[pos];i!=-1;i=edge[i].nxt)65             if(vis[edge[i].v]==0&&dis[edge[i].v]>edge[i].w)66             {67                 dis[edge[i].v]=edge[i].w;68                 q.push(pr(edge[i].v,edge[i].w));69             }70                 71     }72     printf("%d",ans);73 }74 int main()75 {76     read(n);read(m);77     memset(head,-1,sizeof(head));78     for(int i=1;i<=m;i++)79     {80         int x,y,z;81         read(x);read(y);read(z);82         add_edge(x,y,z);83         add_edge(y,x,z);84     }85     prime();86     return 0;87 } 

 

07:清泉-改（prime+堆）