【luogu P1195 口袋的天空】 题解
2024-08-26 10:45:26
题目链接:https://www.luogu.org/problemnew/show/P1195
嗯~我是被题目背景吸引到才做的,想吃棉花糖啦!
话说回来,这道题其实很容易就能想明白,k棵最小生成树。
我们用kruskal的思想,每次连接最小代价的边。假设一开始有n棵树,那么我们每次连接两朵云彩就会减少一棵树。
我们设cnt为生成树的数量,每次连接就会是cnt-1-1-1-1....直到cnt == k,就好啦~
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = ; int n,m,k,fa[maxn],cnt,ans = ; int find(int x)
{
return fa[x] == x?x:fa[x] = find(fa[x]);
} struct edge{
int u,v,w;
}e[maxn]; int cmp(edge a,edge b)
{
return a.w<b.w;
} int main()
{
scanf("%d%d%d",&n,&m,&k); for(int i = ; i <= n; i++)
{
fa[i] = i;
} for(int i = ; i <= m; i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
e[i].u = x;
e[i].v = y;
e[i].w = z;
}
cnt = n;
sort(e+,e++m,cmp); for(int i = ; i <= m; i++)
{
if(cnt <= k) break; int x = find(e[i].u);
int y = find(e[i].v);
if(x!=y)
{
fa[x] = y;
ans += e[i].w;
cnt--;
} } if(cnt == k)
{
printf("%d",ans);
return ;
}
else
{
printf("No Answer");
return ;
}
}
最新文章
- 笔记:Binder通信机制
- Azure Queue Storage 基本用法 -- Azure Storage 之 Queue
- Linux2.6内核进程调度系列--scheduler_tick()函数3.更新普通进程的时间片
- NLP概述
- Win 8.1 下 安装 SQL2005
- AVAudioRecorder、AVAudioPlayer录音及播放
- 小白偶遇Sublime Text 3
- AC自动机——多模式串匹配的算法思想
- JqMobi学习
- BigDecimal-解决商业计算
- JavaWeb学习之JDBC API中常用的接口和类
- and,or
- Spring Data Jpa接口简介
- MapServer Tutorial——MapServer7.2.1教程学习(大纲)
- xcode9 报错 “Swift Language Version” (SWIFT_VERSION) build setting must be set to a supported value for targets which use Swift
- Fiddler怎么可以抓取https的请求包
- mybatis源码解析5---SqlSession解析
- Cracking The Coding Interview 9.7
- 去7JAVA
- 【Android病毒分析报告】- 手机支付毒王“银行悍匪”的前世今生