POJ1258最小生成树简单题
简单 生成 最小
2023-09-11 14:14:00 时间
题意:
给你个图,让你求一颗最小生成树。
思路:
裸题,克鲁斯卡尔或者普利姆都行。
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct
{
int a ,b ,c;
}NODE;
NODE node[100*100+10];
int mer[105];
bool camp(NODE a ,NODE b)
{
return a.c < b.c;
}
int finds(int x)
{
return x == mer[x] ? x : mer[x] = finds(mer[x]);
}
int main ()
{
int n ,i ,j ,ans;
while(~scanf("%d" ,&n))
{
int nowid = 0;
for(i = 1 ;i <= n ;i ++)
{
for(j = 1 ;j <= n ;j ++)
{
nowid++;
scanf("%d" ,&node[nowid].c);
node[nowid].a = i ,node[nowid].b = j;
}
mer[i] = i;
}
sort(node + 1 ,node + nowid + 1 ,camp);
ans = 0;
for(i = 1 ;i <= nowid ;i ++)
{
int x = finds(node[i].a);
int y = finds(node[i].b);
if(x == y) continue;
ans += node[i].c;
mer[x] = y;
}
printf("%d\n" ,ans);
}
return 0;
}
给你个图,让你求一颗最小生成树。
思路:
裸题,克鲁斯卡尔或者普利姆都行。
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct
{
int a ,b ,c;
}NODE;
NODE node[100*100+10];
int mer[105];
bool camp(NODE a ,NODE b)
{
return a.c < b.c;
}
int finds(int x)
{
return x == mer[x] ? x : mer[x] = finds(mer[x]);
}
int main ()
{
int n ,i ,j ,ans;
while(~scanf("%d" ,&n))
{
int nowid = 0;
for(i = 1 ;i <= n ;i ++)
{
for(j = 1 ;j <= n ;j ++)
{
nowid++;
scanf("%d" ,&node[nowid].c);
node[nowid].a = i ,node[nowid].b = j;
}
mer[i] = i;
}
sort(node + 1 ,node + nowid + 1 ,camp);
ans = 0;
for(i = 1 ;i <= nowid ;i ++)
{
int x = finds(node[i].a);
int y = finds(node[i].b);
if(x == y) continue;
ans += node[i].c;
mer[x] = y;
}
printf("%d\n" ,ans);
}
return 0;
}
相关文章
- 最简单 iText 的 PDF 生成方案(含中文解决方案)HTML 转为 PDF
- POJ1789简单小生成树
- POJ1258简单最小生成树
- uniapp - 简单的方式生成app证书(android和ios)
- C#反射实现 C# 反射 判断类的延伸类型 使用代码生成工具Database2Sharp快速生成工作流模块控制器和视图代码 C# ADO.NET的SqlDataReader对象,判断是否包含指定字段 页面中添加锚点的几种方式 .net 简单实用Log4net(多个日志配置文件) C# 常用小点
- 快速排序的Python 简单实现
- 地球引擎保姆级教程——最简单的单点NDVI时序图表!
- 超简单的三管无感无刷三相电机驱动板
- 一步一步教你简单完成 Android USB开发
- spring事务详解(二)简单样例
- 框架Thinkphp5 简单的实现行为 钩子 Hook
- Python 基础 之 多任务 Thread 线程的知识与使用简单整理(线程的创建使用、全局共享资源竞争互斥锁死锁等)
- Vue 之 mockjs 结合 axios 在 vue 中的随机数据生成的简单使用
- Linux 之 Ubuntu 下安装配置ARM交叉编译器(工具链)的简单整理
- MPI编程简单介绍
- iOS - UILabel添加图片之富文本的简单应用
- 思科路由器的密码忘记了用简单的命令来重置思科路由器密码
- leetcode 448. Find All Numbers Disappeared in an Array 找到所有数组中消失的数字(简单)