【[APIO2008]免费道路】
标签：register pre amp line getchar 生成树 max build str
\(kruskal\)好题
\(0\)边的数量在某些情况下是可以无限制的调控的，前提是所有必须存在的边都在生成树里了
所以应该分别求出有哪些边是必须在生成树里的，我们可以先从大到小排序，求出有哪些\(0\)边必须在生成树里，之后再从小到大排序，求出那些\(1\)边必须在生成树里
之后剩下的边就可以随便放了，调控\(0\)边的个数恰好为\(k\)即可
代码
#include
#include
#include
#include
#define LL long long
#define re register
#define maxn 20005
struct E
{
int u,v,w;
}e[100005],Ans[100005];
inline int read()
{
char c=getchar();
int x=0;
while(c‘9‘) c=getchar();
while(c>=‘0‘&&csz[yy]) fa[yy]=xx,sz[xx]+=sz[yy];
else fa[xx]=yy,sz[yy]+=sz[xx];
return 1;
}
inline int cmp1(E A,E B)
{
return A.wB.w;
}
int main()
{
n=read(),m=read(),k=read();
for(re int i=1;ik)
{
puts("no solution");
return 0;
}
std::sort(e+1,e+m+1,cmp1);
Rebuild();
for(re int i=1;i=k) continue;
if(merge(e[i].u,e[i].v))
{
if(!e[i].w&&num
【[APIO2008]免费道路】
标签：register pre amp line getchar 生成树 max build str
原文地址：https://www.cnblogs.com/asuldb/p/10205713.html
评论