蓝桥杯历届试题-国王的烦恼

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h> 

using namespace std;

const int Max_N = 1e4+10;

const int Max_M = 1e5+10;

struct Brige

{

    int u,v;

    int day;

    Brige(){}

    Brige(int u_,int v_,int day_)

    {

        u = u_; v = v_; day = day_;

    }

}brige[Max_M];

int n,m;

int cur_day;

int par[Max_N];

int height[Max_N];

void init(int n);

int find(int x);

void unite(int x, int y);

bool same(int x, int y);

void solve();

bool cmp(const Brige &b1, const Brige &b2);

int main()

{

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

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

    {

        scanf("%d%d%d",&brige[i].u,&brige[i].v,&brige[i].day);

        cur_day = max( cur_day, brige[i].day);

    }

    solve();

    return 0;

}

void init(int n)

{

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

    {

        par[i] = i;

        height[i] = 0;

    }

}

int find( int x )

{

    return x==par[x] ? x : par[x] = find(par[x]);

}

void unite(int x, int y)

{

    x = find(x); y = find(y);

    if( x==y )

        return;

    if( height[x]<height[y] )

    {

        par[x] = y;  

    } 

    else

    {

        par[y] = x;

        if( height[x]==height[y] )    height[x]++;

    }

}

bool same(int x, int y)

{

    return find(x)==find(y);

}

bool cmp(const Brige &b1, const Brige &b2)

{

    return b1.day>b2.day;// 用>=作为条件会出错,原因是?

}

void solve()

{

    init(n);

    sort(brige,brige+m,cmp);

    int i = 0, ans = 0;

    bool flag;

    while( cur_day>0 && i<m )

    {

        flag = false;

        for( ; i<m; i++ )

        {

            if( cur_day != brige[i].day )

            {

                cur_day = brige[i].day;

                break;

            }

            int u = brige[i].u, v = brige[i].v;

            bool temp = same(u,v);

            unite(u,v);

            if( flag )    continue;

            if( temp^same(u,v) )

            {

                ans++;  flag = true;

            }

        }

    }

    printf("%d\n",ans);

}