洛谷 P1195 【口袋的天空】
2024-09-06 09:07:17
P1195
大体题意:
就是给你\(n\)个点\(m\)条边, 然后让你把这几个点连成\(k\)个部分.
解题思路:
很容易就可以想到生成树(别问我怎么想到的).
因为最小生成树中有一个判断
for (int i = 1; i <= m; ++i) {
if (father(ka[i].x) != father(ka[i].y)){
unionn(ka[i].x, ka[i].y);
tot += ka[i].v;
s++;
}
if (s == n - 1) break;//我在这里,如果这张图中已经加入了n-1条边,
}//那就说明图已经可以联通了,然后如果去掉m条边的话,那就是把图分成了m个部分
//那么我们可以利用这一点来用kruskal做这道题聊.
修改后的代码长这样:
for (int i = 1; i <= m; ++i) {
if (father(ka[i].x) != father(ka[i].y)){
unionn(ka[i].x, ka[i].y);
tot += ka[i].v;
s++;
}
if (s == n - k) break;//k为分成多少个部分,自己想一下也很好想.
//n-1条边可以把图刚刚好联通,n-k条边可以将图分成k个部分.
}
code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
int n, m, k, s, cnt, tot;
struct node {
int x, y, v;
}ka[200001];
int fat[5001];
int read() {
int s = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
int father(int x) {
if (fat[x] != x) fat[x] = father(fat[x]);//并查集用
return fat[x];
}
void unionn(int x, int y) {//并查集用
int fa = father(x);
int fb = father(y);
if (fa != fb) fat[fa] = fb;
}
bool cmp(node a, node b) {//sort用
return a.v < b.v;
}
int main() {
n = read(), m = read(), k = read();
int x, y, d;
for (int i = 1; i <= m; i++) {
x = read(), y = read(), d = read();
ka[++cnt].v = d;
ka[cnt].x = x;
ka[cnt].y = y;
}
for (int i = 1; i <= n; i++) fat[i] = i;//并查集用
sort(ka + 1, ka + m + 1, cmp);
for (int i = 1; i <= m; ++i) {//kruskal
if (father(ka[i].x) != father(ka[i].y)){
unionn(ka[i].x, ka[i].y);
tot += ka[i].v;
s++;
}
if (s == n - k) break;
}
printf("%d\n", tot);
}
最新文章
- .NET NLog 详解(五) - Condition Expression
- 移动POS机
- JavaScript验证正则表达式大全
- Cocos2d-x 3.4版本 新建项目 IOS版
- JSF的ui标签
- 【转】话说我打算一天学完object c语法,系列1--------来自书Objective-c程序设计
- OPStackComputeNodeMaintain
- C++静态成员函数不能调用非静态成员变量
- Objextive-C几道小题目笔记
- 玩转Windows服务系列&mdash;&mdash;创建Windows服务
- ubuntu apt-get update 连接不到指定的源
- Python/ selectors模块及队列
- android DialogFragment 实现Dialog展示扫二维码图片展示
- [LeetCode] 1. Two Sum 两数之和
- len()方法
- Unity3D游戏开发框架-资源管理类ResourceManage
- mysql 原理 ~ innodb恢复机制
- SQL Server -- stuff 函数
- [转][CentOS]修改IP后立即生效
- 支持iis高并发