牛客练习赛74 CCA的图(并查集贪心)

本来不算裸题,但是这个数据范围提示的太明显了

先对边按照编号排序

先保证最大

那么我们的边从一直并查集合并,一旦连通就停下来

那么这个一定是最大的

现在我们要求最小

那我们把并查集数组再次初始化,按顺序加边

一旦连通就停下来,此时是最小的

正确性显然....(不显然可以留言)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
struct edge{
    int l,r,w;
    bool operator < (const edge&tmp )    const{
        return w<tmp.w;
    }
}a[maxn*3];
int n,pre[maxn],m,s,t,ansl,ansr;
int find(int x){ return x==pre[x]?x:pre[x]=find(pre[x]);}
void join(int q,int w)
{
    pre[find(q)] = find(w);
}
int main()
{
    cin >> n >> m >> s >> t;
    for(int i=1;i<=n;i++)    pre[i] = i;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].w);
    sort( a+1,a+1+m );
    for(int i=m;i>=1;i--)
    {
        int l = a[i].l, r = a[i].r;
        join(l,r);
        if( find(s)==find(t) )
        {
            ansl = i;
            break;
        }
    }
    for(int i=1;i<=n;i++)    pre[i] = i;
    for(int i=ansl;i<=m;i++)
    {
        int l = a[i].l, r = a[i].r;
        join(l,r);
        if( find(s)==find(t) )
        {
            ansr = i;
            break;
        }        
    }
    cout << a[ansl].w << " " << a[ansr].w;
}