题意：给定一个带权边无向图，求最小生成树，且满足第一个节点的度为固定的k 无解则输出-1
数据规模： 节点数n和限制k<=5000 边数m<=10^5 时限8sec
思路：
首先时限比较宽，第一个想到的暴力做法是枚举第一个节点（即首都）选中的K条边，复杂度为阶乘级别 无法接受。但是我们可以确定，问题的关键在于在所有国道中选择哪k条国道。一旦k条国道选定，最小生成树就是固定的。
考虑一个极端的情况，如果我们直接对这个图运行Kruskal算法，得到了一个树 且 第一个节点的度为k，则这就是正确的答案。当然，一般数据是无法做到的。
那么我们就可以使用一个技巧，如果运行Kruskal算法后第一个节点的度小于k，那么我们在算法运行的序列中将所有国道的位置整体向前移动，使得下一次运行Kruskal算法可以选定更多的国道，我们就离正确答案更近了。反之亦然。
那么怎样调整所有“国道”在Kruskal序列中的位置呢？
选定一个double值mid 它可以很大，也可以很小，在排序时“国道”的权值加上这个mid再与非国道比较，就可以适当的调节所有“国道”在序列中的位置。
代码如下，只要理解了排序比较函数cmp 也就理解了这个Kruskal的变种算法了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=+,maxm=+;
int x[maxm],y[maxm],w[maxm],sig[maxm],ance[maxn],ans[maxn];
int n,m,k,tot,cnt,captedge;
double l,r,mid;
bool cmp(int a,int b)
{
return (w[a]+(x[a]==)*mid)<(w[b]+(x[b]==)*mid);//这个算法的核心
}
int findance(int x)
{
if(x==ance[x])return x;
else return ance[x]=findance(ance[x]);
}
void Kruskal(bool flag)
{
cnt=captedge=;
for(int i=;i<=n;i++)
{
ance[i]=i;
}
sort(sig,sig+m,cmp);
for(int i=;i<m;i++)
{
if(cnt+==n) return ;
int j=sig[i];
int u=findance(x[j]),v=findance(y[j]);
if((u!=v)&&(flag||(captedge+(x[j]==))<=k)) {
ance[u]=v;
ans[cnt++]=j;
if(x[j]==)captedge++;
}
}
}
int main()
{
ios::sync_with_stdio(false);
freopen("t.txt","r",stdin);
cin>>n>>m>>k;
tot=;
for(int i=;i<m;i++)
{
sig[i]=i;
cin>>x[i]>>y[i]>>w[i];
if(x[i]>y[i]){int t=x[i];x[i]=y[i];y[i]=t;}//swap
if(x[i]==)tot++;
}
if((k>tot)||(k==&&n>))
{
cout<<"-1"<<endl;
return ;
}
cnt=;
Kruskal();
if(cnt!=(n-))
{
cout<<"-1"<<endl;
return ;
}
l=(-)*100000.0;
r=100000.0;
while(((l+1e-)<r)&&(captedge!=k))
{
mid=(l+r)/2.0;
Kruskal();
if(captedge<k)r=mid;
else l=mid;
}
if(captedge!=k)mid=(l+r)/2.0;
Kruskal();
cout<<n-<<endl;
if(cnt>=)cout<<ans[]+;
for(int i=;i<cnt;i++)
cout<<" "<<ans[i]+;
cout<<endl;
return ;
}