[APIO2008]免费道路

2021-07-12 12:07

阅读：720

标签：str pac getchar http val 转化 getch int lock

技术分享图片

因为粗心WA了好多次

快要联赛了我好像状态越来越废了==

最小生成树好题

题目可以转化为让你选n-1条边连通整个图

必须选择正好k条0边

直接暴力选择k条0边是不可行的，因为会有一些必选情况无法处理

所以我们先把所有的1边都连上

然后看有哪些0边是必须要连上的

记录下这些0边

然后这些0边是必须要选择的

然后继续选够k条0边

然后剩下的1边就肯定能把整张图连通起来辣

所以剩下的直接跑个最小生成树就行了

#include
#include
#include
#include
const int M = 100005 ;
const int N = 500005 ;
using namespace std ;
inline int read() {
    char c = getchar() ; int x = 0 , w = 1 ;
    while(c>'9'||c='0' && c b.val ; }
inline bool fir0(E a , E b) { return a.val  k || tot

[APIO2008]免费道路

标签：str pac getchar http val 转化 getch int lock

原文地址：https://www.cnblogs.com/beretty/p/9601135.html

上一篇：WebApi 运行原理

下一篇：windows下用pycharm安装tensorflow简易教程

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[APIO2008]免费道路
文章链接：http://soscw.com/index.php/essay/104155.html

亲，登录后才可以留言！

[APIO2008]免费道路

评论

热门文章

推荐文章

最新文章

置顶文章