CODEFORCES 125E MST Company 巧用Kruskal算法-白红宇

CODEFORCES 125E MST Company 巧用Kruskal算法

阅读量：4329 次

发布时间：2019-06-06

本文共 1472 字，大约阅读时间需要 4 分钟。

题意：给定一个带权边无向图，求最小生成树，且满足第一个节点的度为固定的k 无解则输出-1

数据规模：节点数n和限制k<=5000 边数m<=10^5 时限8sec

思路：

首先时限比较宽，第一个想到的暴力做法是枚举第一个节点（即首都）选中的K条边，复杂度为阶乘级别无法接受。但是我们可以确定，问题的关键在于在所有国道中选择哪k条国道。一旦k条国道选定，最小生成树就是固定的。

考虑一个极端的情况，如果我们直接对这个图运行Kruskal算法，得到了一个树且第一个节点的度为k，则这就是正确的答案。当然，一般数据是无法做到的。

那么我们就可以使用一个技巧，如果运行Kruskal算法后第一个节点的度小于k，那么我们在算法运行的序列中将所有国道的位置整体向前移动，使得下一次运行Kruskal算法可以选定更多的国道，我们就离正确答案更近了。反之亦然。

那么怎样调整所有“国道”在Kruskal序列中的位置呢？

选定一个double值mid 它可以很大，也可以很小，在排序时“国道”的权值加上这个mid再与非国道比较，就可以适当的调节所有“国道”在序列中的位置。

代码如下，只要理解了排序比较函数cmp 也就理解了这个Kruskal的变种算法了。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 using namespace std;10 const int maxn=5000+1,maxm=100000+1;11 int x[maxm],y[maxm],w[maxm],sig[maxm],ance[maxn],ans[maxn];12 int n,m,k,tot,cnt,captedge;13 double l,r,mid;14 bool cmp(int a,int b)15 {16 return (w[a]+(x[a]==1)*mid)<(w[b]+(x[b]==1)*mid);//这个算法的核心 17 }18 int findance(int x)19 {20 if(x==ance[x])return x;21 else return ance[x]=findance(ance[x]);22 }23 void Kruskal(bool flag)24 {25 cnt=captedge=0;26 for(int i=1;i<=n;i++)27 {28 ance[i]=i;29 }30 sort(sig,sig+m,cmp);31 for(int i=0;i
             
              >n>>m>>k;50 tot=0;51 for(int i=0;i
              
               >x[i]>>y[i]>>w[i];55 if(x[i]>y[i]){ int t=x[i];x[i]=y[i];y[i]=t;}//swap 56 if(x[i]==1)tot++;57 }58 if((k>tot)||(k==0&&n>1))59 {60 cout<<"-1"<
               
                =1)cout<

转载于:https://www.cnblogs.com/heisenberg-/p/6341406.html

你可能感兴趣的文章