APIO2008免费道路
2021-05-18 14:28
阅读：694
标签：生成 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
评论
亲，登录后才可以留言！