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

解题思路:

tips：题目中的抗议天数的意思是当某两个小岛不可达的当天会抗议，所有抗议的天数相加即为所得！

按照天数递减的顺序建树，只要判断两个点不联通并且前一个处理的和当前的不在同一天，那么天数就加1；

注意事项:





参考代码:

#include<iostream>  
#include<cstring>  
#include<vector>  
#include<algorithm>  
using namespace std;  
  
struct edge{  
    int u,v,day;  
    friend bool operator <(edge e1,edge e2)  
    {  
        return e1.day>e2.day;  
    }  
};  
vector<edge>edges;  
int n,m,pre,cnt,ans,f[11000];  
int find(int x)  
{  
    return f[x]<0?x:f[x]=find(f[x]);  
}  
int merge(int x,int y)  
{  
    int rx=find(x);int ry=find(y);  
    if(rx!=ry)  
    {  
        f[rx]+=f[ry];  
        f[ry]=rx;  
        return 1;  
    }  
    return 0;  
}  
int main()  
{  
    cin>>n>>m;cnt=n;   
    for(int i=1;i<=m;i++)  
    {  
        int x,y,z;cin>>x>>y>>z;  
        edges.push_back(edge{x,y,z});  
    }  
    sort(edges.begin(),edges.end());  
      
    memset(f,-1,sizeof(f));  
    pre=-1 ;  
    for(int i=0;i<edges.size();i++)  
    {  
        int x=edges[i].u;int y=edges[i].v;int d=edges[i].day;  
        if(merge(x,y)&&d!=pre)  
        {  
            ans++;   
            pre=d;  
            if(--cnt==1)break;  
        }  
    }  
    cout<<ans<<endl;  
    return 0;  
}