Codeforces 362D Fools and Foolproof Roads

时间:2021-12-21 07:28:32

Fools and Foolproof Roads

并查集瞎搞搞就行, 有点小坑点。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 2e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int n, m, p, q, num, fa[N], U = -, V = -;
LL cost[N];
vector<PII> vc; int getRoot(int x) {
return fa[x] == x ? x : fa[x] = getRoot(fa[x]);
} int main() {
scanf("%d%d%d%d", &n, &m, &p, &q);
for(int i = ; i <= n; i++) fa[i] = i;
for(int i = ; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
U = u; V = v;
int x = getRoot(u);
int y = getRoot(v);
if(x == y) {
cost[x] += w;
} else {
fa[x] = y;
cost[y] += cost[x] + w;
}
}
priority_queue<PLI, vector<PLI>, greater<PLI> > que;
for(int i = ; i <= n; i++)
if(getRoot(i) == i) que.push(mk(cost[i], i)), num++;
int need = num - q;
if(need < || need > p) {
puts("NO");
return ;
}
while(need--) {
p--;
int u = que.top().se; que.pop();
int v = que.top().se; que.pop();
int x = getRoot(u), y = getRoot(v);
vc.push_back(mk(u, v));
U = u, V = v;
LL ret = min(1000000000ll, cost[x] + cost[y] + );
cost[y] += cost[x] + ret;
que.push(mk(cost[y], y));
}
if(p && U == -) {
puts("NO");
return ;
}
while(p--) {
vc.push_back(mk(U, V));
}
puts("YES");
for(auto& t : vc) printf("%d %d\n", t.fi, t.se);
return ;
} /*
*/

Codeforces 362D Fools and Foolproof Roads的更多相关文章

  1. Codeforces 362D Fools and Foolproof Roads 构造题

    题目链接:点击打开链接 题意: 给定n个点 m条边的无向图 须要在图里添加p条边 使得图最后连通分量数为q 问是否可行,不可行输出NO 可行输出YES,并输出加入的p条边. set走起.. #incl ...

  2. Codeforces Round &num;212 &lpar;Div&period; 2&rpar; D&period; Fools and Foolproof Roads 并查集&plus;优先队列

    D. Fools and Foolproof Roads   You must have heard all about the Foolland on your Geography lessons. ...

  3. Codeforces 191C Fools and Roads&lpar;树链拆分&rpar;

    题目链接:Codeforces 191C Fools and Roads 题目大意:给定一个N节点的数.然后有M次操作,每次从u移动到v.问说每条边被移动过的次数. 解题思路:树链剖分维护边,用一个数 ...

  4. Codeforces GYM 100876 J - Buying roads 题解

    Codeforces GYM 100876 J - Buying roads 题解 才不是因为有了图床来测试一下呢,哼( 题意 给你\(N\)个点,\(M\)条带权边的无向图,选出\(K\)条边,使得 ...

  5. Codeforces Gym 100338C C - Important Roads tarjan

    C - Important RoadsTime Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudge/contes ...

  6. 【CodeForces 567E】President and Roads(最短路)

    Description Berland has n cities, the capital is located in city s, and the historic home town of th ...

  7. Codeforces &num;369 div2 D&period;Directed Roads

    D. Directed Roads time limit per test2 seconds memory limit per test256 megabytes inputstandard inpu ...

  8. CodeForces &num;369 div2 D Directed Roads DFS

    题目链接:D Directed Roads 题意:给出n个点和n条边,n条边一定都是从1~n点出发的有向边.这个图被认为是有环的,现在问你有多少个边的set,满足对这个set里的所有边恰好反转一次(方 ...

  9. codeforces 427 div&period;2 F&period; Roads in the Kingdom

    F. Roads in the Kingdom time limit per test 2 seconds memory limit per test 256 megabytes input stan ...

随机推荐

  1. 天河2号荣膺第41届TOP500榜首

    国际TOP500组织在6月17日公布最新全球超级计算机500强榜单,由中国国防科技大学研制的“天河二号”以每秒33.86千万亿次的浮点运算速度成为全球最快的超级计算机. 天河2号(又称银河2号),将在 ...

  2. 设计模式——Spring IoC中用到的模板方法模式

    基本概念 什么是模板方法(Template method):父类定义了骨架(调用哪些方法及顺序),某些特定方法由子类实现. 最大的好处:代码复用,减少重复代码.除了子类要实现的特定方法,其他方法及方法 ...

  3. SpringMVC——对Ajax的处理(包含 JSON 类型)

    一.首先要搞明白的一些事情. 1.从客户端来看,需要搞明白: (1)要发送什么样格式的 JSON 数据才能被服务器端的 SpringMVC 很便捷的处理,怎么才能让我们写更少的代码,如何做好 JSON ...

  4. 【Bootstrap基础学习】01 Bootstrap的CSS

    Bootstrap 使用了一些 HTML5 元素和 CSS 属性,所以需要使用 HTML5 文档类型. <!DOCTYPE html> <html lang="zh-CN& ...

  5. Linux时间函数

    一.时间编程 1.核心理论 (1).时间类型 2.函数学习 (1).获取日历时间 函数名:time 函数原型:time_t time(time_t *t) 函数功能:获取当前日历时间 所属头文件:&l ...

  6. 前端-mate讲解

    <meta> 元素可提供有关页面的元信息(meta-information),比如针对搜索引擎和更新频度的描述和关键词. <meta> 标签位于文档的头部,不包含任何内容. & ...

  7. &period;net Core连接MongoDB

    前两天在学习MongoDB相关的知识,做了个小Demo,大概是省份里面有多少所学校 连接MongoDB首先要通过Nuget添加一个MongoDB的包,下载此包 安装完毕后开始写代码了,创建一个省份实体 ...

  8. SDVN

    Software Defined Vehicular Networks VANET 车载自组网(VANET)是指在交通环境中车辆之间.车辆与固定接入点之间及车辆与行人之间相互通信组成的开放式移动Ad ...

  9. 如何在苹果手机上安装自制的AD证书

    写这篇博文的契机是有人已经实现了CRM在用自制证书部署IFD后,在手机安装上自制证书后即可登录官方移动端APP,因为之前很多人都尝试过只要是自制证书部署的IFD就无法使用官网手机APP,而本人实验下来 ...

  10. Arduino IDE for ESP8266教程(0)配置IDE

    淘宝链接 https://detail.tmall.com/item.htm?id=540067174120&spm=a1z09.2.0.0.6f7c6509ujAvQs&_u=71q ...