07:清泉-改（prime+堆）

时间限制:: 10000ms
单个测试点时间限制:: 1000ms
内存限制:: 512000kB

描述

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

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

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

输入

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

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

输出

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

样例输入

样例输出

提示

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

来源

laekov

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int MAXN=;

 const int maxn=0x3f;

 void read(int &n)

 {

     char c='+';int x=;bool flag=;

     while(c<''||c>''){c=getchar();if(c=='-')flag=;}

     while(c>=''&&c<='')

     x=(x<<)+(x<<)+c-,c=getchar();

     flag==?n=-x:n=x;

 }

 struct node

 {

     int u,v,w,nxt;

 }edge[MAXN];

 int head[MAXN];

 int num=;

 int add_edge(int x,int y,int z)

 {

     edge[num].u=x;

     edge[num].v=y;

     edge[num].w=z;

     edge[num].nxt=head[x];

     head[x]=num++;

 }

 int n,m;

 int vis[MAXN];

 int dis[MAXN];

 struct pr

 {

     int p,v;

     pr()

     {p=v=;}

     pr(int a,int b)

     {p=a;v=b;}

     bool operator<(const pr&a)const

     {return v>a.v;}

 }inc;

 void prime()

 {

     //vis[1]=1;

     priority_queue<pr>q;

     memset(dis,maxn,sizeof(dis));

     dis[]=;

     q.push(pr(,));

     int ans=;

 //    for(int i=head[1];i!=-1;i=edge[i].nxt)

 //        q.push(pr(edge[i].v,edge[i].w));

     for(int k=;k<=n;k++)

     {

         int pos;

         while(vis[q.top().p]&&q.size()>=)

             q.pop();

         pos=q.top().p;

         vis[pos]=;

         ans+=dis[pos];

         for(int i=head[pos];i!=-;i=edge[i].nxt)

             if(vis[edge[i].v]==&&dis[edge[i].v]>edge[i].w)

             {

                 dis[edge[i].v]=edge[i].w;

                 q.push(pr(edge[i].v,edge[i].w));

             }

     }

     printf("%d",ans);

 }

 int main()

 {

     read(n);read(m);

     memset(head,-,sizeof(head));

     for(int i=;i<=m;i++)

     {

         int x,y,z;

         read(x);read(y);read(z);

         add_edge(x,y,z);

         add_edge(y,x,z);

     }

     prime();

     return ;

 }

巴特西

07:清泉-改（prime+堆）

最新文章

热门文章