蓝桥杯历届试题-国王的烦恼-题解（C语言代码）

解题思路:

注意事项:

参考代码:

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

int n,m;    //n个岛,m座桥

int ans;    //抗议天数

int num;    //有效桥个数

struct land

{

   int x;    //起点

   int y;    //终点

   int t;    //桥的天数

};

land island[100005];    //最多有十万座桥

int f[10005];    //并查集的数组

int last_time;

void Init ()

{

   for(int i=0;i<n;i++)

   {

       f[i]=i;

   }

}

bool cmp(land x,land y)

{

   return x.t>y.t;

}

int getf(int x)

{

    if(x==f[x])    //如果并查集下标等于内部值,代表它就是根

   {

       return x;

   }

    else

   {

        f[x]=getf(f[x]);    //沿途遍历的元素全部归到根,即为路径压缩

        return f[x];

   }

}

int merge(int v,int u)

{

   //判断是否同根,同根则代表已连通,不同根代表未连通,这是有效桥

   int t1,t2;

   t1=getf(v);    //getf函数用来找寻其根

   t2=getf(u);

   if(t1!=t2)    //如果不同根

   {

       f[t2]=t1;    //t2及t2后代全部归到t1

       return 1;

   }

   return 0;    //同根则返回假

}

int main()

{

   //1.输入全部的桥

   //2.初始化并查集

   //3.将桥按桥的时间从大到小排序

   //4.将m行指令枚举

   //5.如果输入的桥的根和要连接的桥不属于同一个根,代表不属于同一个集合

   //  那么说明有新的"可以让原集合连接到外处"的桥出现了(同一个集合内的岛可以相互达到,看作为一体的),我们称之为有效桥

   //6. 如果有"有效桥"出现了,那么我们记录这个桥的时间,如果该"有效桥"的时间和前一座"有效桥"的时间不同,那么投诉天数加一

   //7.如果时间相同,代表同一天出现两座桥，但是居民只会抱怨一天

   //8.**核心**:逆向思维,按照天数递减的顺序建树,如果之前没有这座桥,突然有这座桥了,那么就会抱怨

   scanf("%d %d",&n,&m);

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

   {

       scanf("%d %d %d",&island[i].x,&island[i].y,&island[i].t);

   }

   Init();    //将并查集初始化

   sort(island,island+m,cmp);

   for(int i=0;i<m;i++)    //枚举m座桥

   {

       if(merge(island[i].x,island[i].y))    //如果这两个点没有被连通,那么就是有效桥

       {

           //出现有效桥了,就对比一下是否与上一次的有效桥时间相等。

           if(island[i].t!=last_time)

           {

               ans++;

               last_time=island[i].t;//记录下它的时间,同时间的桥只能抗议一次

           }

           num++;    //num代表有效桥的数量

       }

       if(num==n-1)    //如果达成最少边的生成树,既全部岛已连通就不用再判断了

       {

           break;

       }

   }

   printf("%d",ans);

   return 0;

}