复习--最小生成树&&并查集
2024-08-31 03:01:18
我个人比较喜欢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 ;
}
最新文章
- js 对Array的补充
- Mysql5.6主从热备配置
- js事件(一)之事件流
- nginx下面server配置
- linux的<;pthread.h>;
- linux下cp目录时排除一个或者多个目录的方法
- 常见的HTTP错误总结
- 服务端 unity
- 《c程序设计语言》读书笔记--首次输入不能是空符;最多10个字符
- STM32硬件复位时间
- sift算法c语言实现
- Eclipse 修改maven 仓储Repository位置
- 【Redis】LRU算法和Redis的LRU实现
- Python自学:第三章 倒着打印列表
- 电子签名在K2中的应用
- python学习Day1 计算机原理编程思维
- 使用yield返回IEnumber<;T>;集合
- <;基础>; PHP 进阶之 类型转换
- 关于Android系统的启动流程
- <;要做股市赢家:杨百万>;读书笔记