我个人比较喜欢Kruskal算法,所以就把这个方法写了一下,但过不了洛谷,70分。

思路是先全读入,再排序,一条一条加边。运用并查集。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct s{
int h;
int t;
int w;
};
int fa[];
bool cmp(s a,s b)
{
return a.w < b.w;
}
int find(int a)
{
if(fa[a] != a) //不是while
fa[a] = find(fa[a]);
return fa[a];
}
void un(int a,int b)
{
a = find(a);
b = find(b);
if(a != b)
fa[b] = a;
}
bool judge(int a,int b)
{
a = find(a);
b = find(b);
if(a != b)
return false;
else return true;
}
s side[];
int m,n,k,tot = ,num = ;
int main()
{
cin>>n>>k;
for(int i = ;i <= n;i++)
{
fa[i] = i;
}
for(int i = ;i <= k;i++)
{
cin>>side[i].h>>side[i].t>>side[i].w;
//tot += side[i].w;
}
sort(side + ,side + k + ,cmp);
tot = ;
for(int i = ;i <= k;i++)
{
if(judge(side[i].h,side[i].t) == false)
{
un(side[i].h,side[i].t);
tot += side[i].w;
num++;
}
if(num == n)
break;
}
cout<<tot<<endl;
return ;
}
/*
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
*/

再加一个并查集的板子,日后备用。

#include<iostream>
using namespace std;
int fa[],m,n,x,y,z;
int find(int a)
{
if(fa[a] != a)
fa[a] = find(fa[a]);
return fa[a];
}
bool judge(int a,int b)
{
a = find(a);
b = find(b);
if(a != b)
return false;
else
return true;
}
void un(int a,int b)
{
a = find(a);
b = find(b);
if(a != b)
fa[b] = a;
}
int main()
{
cin>>m>>n;
for(int i = ;i < m;i++)
fa[i] = i;
for(int i = ;i <n;i++)
{
cin>>x>>y>>z;
if(x == )
{
if(judge(y,z) == false)
un(y,z);
}
else
{
if(judge(y,z) == true)
cout<<"Yeah"<<endl;
else
cout<<"No,opps"<<endl;
}
}
return ;
}

最新文章

  1. js 对Array的补充
  2. Mysql5.6主从热备配置
  3. js事件(一)之事件流
  4. nginx下面server配置
  5. linux的&lt;pthread.h&gt;
  6. linux下cp目录时排除一个或者多个目录的方法
  7. 常见的HTTP错误总结
  8. 服务端 unity
  9. 《c程序设计语言》读书笔记--首次输入不能是空符;最多10个字符
  10. STM32硬件复位时间
  11. sift算法c语言实现
  12. Eclipse 修改maven 仓储Repository位置
  13. 【Redis】LRU算法和Redis的LRU实现
  14. Python自学:第三章 倒着打印列表
  15. 电子签名在K2中的应用
  16. python学习Day1 计算机原理编程思维
  17. 使用yield返回IEnumber&lt;T&gt;集合
  18. &lt;基础&gt; PHP 进阶之 类型转换
  19. 关于Android系统的启动流程
  20. &lt;要做股市赢家:杨百万&gt;读书笔记

热门文章

  1. 清除Linux系统多余引导选项
  2. django-Celery分布式队列简单使用
  3. img、a标签的使用
  4. 【原】Python学习_Django搭建环境及创建第一个项目
  5. 解决高分屏/高DPI下GNOME3/Linux字体和按钮太小的问题
  6. Cent os常见操作命令
  7. 02. 爬取get请求的页面数据
  8. ActiveMQ学习总结(1)——ActiveMQ快速入门
  9. [BZOJ 4999]This Problem Is Too Simple!
  10. 洛谷 P2486 BZOJ 2243 [SDOI2011]染色