APIO2008免费道路

2021-05-18 14:28

阅读：599

标签：生成 strong pac 最小生成树 http bool kruskal 最小 printf

题目大意

给定一张n个点m条边的图,图上有两种边,求保证有k条第一种边的情况下的最小生成树
传送门

题解

考虑最小生成树kruskal算法
先找到不含限制的最小生成树,然后就可以知道哪些第一种边是必选的
然后跑第二遍kruskal,先把第一种边加到k条,然后加入第二种边就好

代码

#include
#define inf 1000000000
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&chK)
    {
        puts("no solution");
        return 0;
    }
    top=0;num[0]=num[1]=0;
    for(int i=1;i

APIO2008免费道路

标签：生成 strong pac 最小生成树 http bool kruskal 最小 printf

原文地址：https://www.cnblogs.com/yzhx/p/11740993.html

上一篇：HTTP与HTTPS的区别

下一篇：tomcat windows 平台启动时控制台乱码

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

亲，登录后才可以留言！

APIO2008免费道路

题目大意

题解

代码

评论

热门文章

推荐文章

最新文章

置顶文章