CODEFORCES 125E MST Company 巧用Kruskal算法

题意：给定一个带权边无向图，求最小生成树，且满足第一个节点的度为固定的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 ;
 }