hihocoder#1098 : 最小生成树二·Kruscal算法
2024-09-29 11:25:08
#1098 : 最小生成树二·Kruscal算法
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
随着小Hi拥有城市数目的增加，在之间所使用的Prim算法已经无法继续使用了——但是幸运的是，经过计算机的分析，小Hi已经筛选出了一些比较适合建造道路的路线，这个数量并没有特别的大。
所以问题变成了——小Hi现在手上拥有N座城市，且已知其中一些城市间建造道路的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。
提示：积累的好处在于可以可以随时从自己的知识库中提取想要的！
输入
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为2个整数N、M，表示小Hi拥有的城市数量和小Hi筛选出路线的条数。
接下来的M行，每行描述一条路线，其中第i行为3个整数N1_i, N2_i, V_i，分别表示这条路线的两个端点和在这条路线上建造道路的费用。
对于100%的数据，满足N<=10^5, M<=10^6，于任意i满足1<=N1_i, N2_i<=N, N1_i≠N2_i, 1<=V_i<=10^3.
对于100%的数据，满足一定存在一种方案，使得任意两座城市都可以互相到达。
输出
对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。
- 样例输入
-
5 29
1 2 674
2 3 249
3 4 672
4 5 933
1 2 788
3 4 147
2 4 504
3 4 38
1 3 65
3 5 6
1 5 865
1 3 590
1 4 682
2 4 227
2 4 636
1 4 312
1 3 143
2 5 158
2 3 516
3 5 102
1 5 605
1 4 99
4 5 224
2 4 198
3 5 894
1 5 845
3 4 7
2 4 14
1 4 185 - 样例输出
-
92 板子，稀疏图用比较好
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector> using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-10
typedef long long ll;
const int maxn = 1e6+;
const int mod = 1e9 + ;
int gcd(int a, int b) {
if (b == ) return a; return gcd(b, a % b);
} int par[maxn];
void init(int V)
{
for(int i=;i<=V;i++)
par[i]=i;
}
int find(int x)
{
if(par[x]==x)
return x;
else
return par[x]=find(par[x]);
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)
par[y]=x;
}
bool same(int x,int y)
{
return find(x)==find(y);
}
struct edge
{
int u,v,cost;
}; bool comp(const edge& e1,const edge& e2)
{
return e1.cost<e2.cost;
}
edge es[maxn];
int V,E; int kruskal()
{
sort(es+,es+E+,comp);
int res=;
for(int i=;i<=E;i++)
{ edge e=es[i]; if(!same(e.u,e.v))
{
unite(e.u,e.v);
res+=e.cost;
}
}
return res;
}
int main()
{
scanf("%d%d",&V,&E);
init(V);
for(int i=;i<=E;i++)
{
int a,b,l;
scanf("%d%d%d",&a,&b,&l);
es[i].u=a;
es[i].v=b;
es[i].cost=l;
}
printf("%d\n",kruskal());
return ;
}
最新文章
- js原生碰撞检测
- HDU-1231 简单dp，连续子序列最大和，水
- A New Effect About My Plugin render
- mysqlbinlog -v --base64-output 与不加的区别
- 使用 powershell 的 grep 过滤文本
- hiho 1015 KMP
- mysql 初始化时root无密码
- 什么是RESTful？
- Python 判断闰年，判断日期是当前年的第几天
- AC自动机模板2（【CJOJ1435】）
- Windows核心编程第二章,字符串的表示以及宽窄字符的转换
- Microsoft.AspNet.Web.Optimization.Bundle的完美替换方案
- 初学Python——字符串相关操作
- vue插件开发实践与要点
- mongodb并列查询,模糊查询
- R语言学习 第五篇：字符串操作
- Linux系统编程手册-源码的使用
- PHP:第一章——按位运算和求余运算（判断奇偶数）
- [LuoguP1462]通往奥格瑞玛的道路（$SPFA+$二分）
- 教程-TObjectList.Clear、TStringList.Clear方法对象有没有被释放