【BZOJ3624】【APIO2008】免费道路 [生成树][贪心]

免费道路

Time Limit: 2 Sec  Memory Limit: 128 MB
[Submit][Status][Discuss]

Description

　　

Input

　　

Output

　　

Sample Input

　　5 7 2
　　1 3 0
　　4 5 1
　　3 2 0
　　5 3 1
　　4 3 0
　　1 2 1
　　4 2 1

Sample Output

　　3 2 0
　　4 3 0
　　5 3 1
　　1 2 1

HINT

　　1<=n<=20000,1<=m<=100000,0<=k<=n-1

Main idea

　　一种0边，一种1边，求一棵最小生成树并且正好有K条0边，输出其中一种方案。

Solution

　　显然要搞一棵符合题目的生成树。

　　每次要加入0边或者1边，直接做肯定不可行，考虑有什么0边是一定要加入的。

　　只需要输出一种方案，所以我们先加入所有可加的1边，如果图不联通则加入可加入的0边，那么这几条0边在我们所求的方案中是一定需要加入的。

　　这时候判断一下，如果此时加入的0边数量>K，或者图还是无法联通的话则无解。然后处理完毕前半部分，考虑接下来如何实现。

　　因为我们要使得图为树并且正好有K条0边，运用贪心，想到了加入0边到K条位置（如果到不了K条则也无解），然后剩下的用1边来填。

　　验证一下这样做的可行性：由于我们在前半部分使得了可以成为一棵树，那么显然我们在后半部分中每加入一条0边，则在前半部分中一定有一条1边可以替换使得可行（因为前半部分是尽量加入1边）。每次连边判环运用Krusal即可。

Code

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 const int ONE=;

 const int INF=;

 int n,m,k;

 int Edge_k;

 int fa[ONE];

 int num;

 int Choose[ONE];

 int ans_num;

 int the0;

 struct power

 {

         int x,y,v;

 }a[ONE],Ans_edg[ONE];

 int get()

 {

         int res,Q=;    char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 int find(int x)

 {

         if(fa[x]!=x) fa[x]=find(fa[x]);

         return fa[x];

 }

 void Un(int a,int b)

 {

         int a1=find(a);

         int b1=find(b);

         if(a1!=b1) fa[a1]=b1;

 }

 int Add_set(int N,int v,int ci)

 {

         int kd=;

         for(int i=;i<=m;i++)

           {

               if(kd>=N) break;

               if(a[i].v!=v) continue;

               int x=a[i].x,y=a[i].y;

               if(find(x)!=find(y))

               {

                   Un(x,y);

                   if(ci>=)    Ans_edg[++ans_num]=a[i];

                   if(ci==)

                   {

                       Choose[++num]=i;

                 }

                 Edge_k++;

                 kd++;

                 if(ci==) the0++;

             }

             if(Edge_k==n-) break;

         }

 }

 int main()

 {

           n=get();    m=get();    k=get();

           for(int i=;i<=n;i++) fa[i]=i;

         for(int i=;i<=m;i++)

         {

             a[i].x=get();    a[i].y=get();    a[i].v=get();

         }

           Edge_k=;

           Add_set(INF,,);

           Add_set(INF,,);

           if(Edge_k<n- || num>k)

           {

               printf("no solution\n");

               return ;

         }

           Edge_k=;

           for(int i=;i<=n;i++) fa[i]=i;

           for(int i=;i<=num;i++)

           {

               int x=Choose[i];

               Un(a[x].x,a[x].y);

             Edge_k++;

             if(Edge_k==n-) break;

         }

           Add_set(k-num,,);

         if(the0!=k-num)

           {

               printf("no solution\n");

             return ;

         }

           Add_set(INF,,);

           for(int i=;i<=ans_num;i++)

           {

               printf("%d %d %d\n",Ans_edg[i].x,Ans_edg[i].y,Ans_edg[i].v);

         }

 }