https://www.zybuluo.com/ysner/note/1294305
题面
求一种特殊的最小生成树。给定一个有(n)个节点和(m)条边的图，找出一个生成树满足从根节点(1)直接连向其余节点的边要恰好(k)条，在此条件下生成树的权值和最小。
- (nleq5000,mleq10^5)
解析
这道题思路和[国家集训队2]Tree I是一样的。
不过蒟蒻被卡细节了。。。
- 在已经加上(k)条特殊边后，应该强制跳过特殊边。
- 最终答案中特殊边小于(k)或是凑不出(n-1)条边即为无解。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define db double
#define eps 1e-5
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
int n,m,k,f[N],sta[N],top;
bool use[N];
struct dat{int u,v,w,t,id;bool operator < (const dat &o) const {return (w<o.w)||(w==o.w&&t<o.t);}}a[N<<1],b[N<<1];
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
il int check(re int x,re int op)
{
re int tag=0;top=0;
fp(i,1,n) f[i]=i;
fp(i,1,m)
{
a[i]=b[i];
if(!a[i].t) a[i].w+=x;
}
sort(a+1,a+1+m);
fp(i,1,m)
{
re int u=find(a[i].u),v=find(a[i].v);
if(u^v)
{
if(tag==k&&!a[i].t) continue;
f[v]=u;tag+=(a[i].t==0);
sta[++top]=a[i].id;
}
}
if(!op) return tag>=k;
else return tag;
}
int main()
{
n=gi();m=gi();k=gi();
fp(i,1,m)
{
a[i].u=gi(),a[i].v=gi(),a[i].w=gi();a[i].t=(a[i].u!=1&&a[i].v!=1);a[i].id=i;
b[i]=a[i];
}
re ll l=-1e5-5,r=1e5+5,gu=1e9;
while(l<=r)
{
re db mid=l+r>>1;
if(check(mid,0)) gu=mid,l=mid+1;
else r=mid-1;
}
//printf("%d
",check(gu,1));
if(check(gu,1)!=k||top<n-1) return puts("-1"),0;
printf("%d
",n-1);
fp(i,1,top) printf("%d ",sta[i]);puts("");
return 0;
}