07:清泉-改(prime+堆)

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

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

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

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

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

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

2 2
1 2 2
2 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 node
18 {
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 pr
35 {
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 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏简书专栏

基于tensorflow的一元一次方程回归预测

安装tensorflow命令:pip install tensorflow 下面一段代码能够成功运行,则说明安装tensorflow环境成功。

1074
来自专栏小樱的经验随笔

51 Nod 1007 正整数分组【类01背包】

1007 正整数分组 基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题 将一堆正整数分为2组,要求2组的和相差最小。 例如:1...

2917
来自专栏C语言及其他语言

【每日一题】蛇行矩阵

题号:1097 题目描述 蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。 输入 本题有多组数据,每组数据由一个正整数N组成。(N不大于100) 输出...

3438
来自专栏人工智能LeadAI

Python 设计模式初探

本文章是在阅读精通Python设计模式(中文版)(https://book.douban.com/subject/26829015/),以及阅读 Mask R-...

3606
来自专栏mathor

枚举+优化(8)——前缀和2

2565
来自专栏数据结构与算法

11:大整数减法

11:大整数减法 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 求两个大的正整数相减的差。 输入共2行,第1行是被减...

28910
来自专栏应兆康的专栏

100个Numpy练习【3】

翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

43910
来自专栏null的专栏

算法类面试题解析——美团2016校招:棋子翻转

题目来自伯乐在线,欢迎有不同答案的同学来一起讨论。 ? 分析: 本题主要是二维数组的操作,对指定的位置上的数字进行翻转,其具体过程如下所示: ? 其基本的过程...

2887
来自专栏应兆康的专栏

100个Numpy练习【3】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

5019
来自专栏wOw的Android小站

[Tensorflow] 在Android运行TensorFlow模型

以下代码来自于TensorFlowObjectDetectionAPIModel.java

6101

扫码关注云+社区

领取腾讯云代金券