P1525 关押罪犯 10分求调

OIER__Tym2011 @ 2024-10-06 15:41:27

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int fa[N],a[N],b[N],c[N];
struct z{
    int a,b,c;
}st[N];
bool cmp(z c1,z c2){
    return c1.c>c2.c;
}
int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void bing(int x,int y){
    fa[find(x)]=find(y);
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int j=1;j<=2*n;j++){
        fa[j]=j;
    }
    for(int i=1;i<=m;i++){
        cin>>st[i].a>>st[i].b>>st[i].c;
    }
    sort(st+1,st+1+m,cmp);
    for(int i=1;i<=m;i++){
        int xx=st[i].a,yy=st[i].b;
        bing(xx,2*yy);
        bing(yy,2*xx);
        if(find(xx)==find(2*xx) || find(yy)==find(2*yy)){
            cout<<st[i].c;
            return 0;
        }
    }
    cout<<0;
    return 0;
}

by goIdie @ 2024-10-06 15:56:15

@OIER__Tym2011 应为n+xx和n+yy,不是2*yy和2*xx

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int fa[N],a[N],b[N],c[N];
struct z{
    int a,b,c;
}st[N];
bool cmp(z c1,z c2){
    return c1.c>c2.c;
}
int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void bing(int x,int y){
    fa[find(x)]=find(y);
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int j=1;j<=2*n;j++){
        fa[j]=j;
    }
    for(int i=1;i<=m;i++){
        cin>>st[i].a>>st[i].b>>st[i].c;
    }
    sort(st+1,st+1+m,cmp);
    for(int i=1;i<=m;i++){
        int xx=st[i].a,yy=st[i].b;
        bing(xx,n+yy);
        bing(yy,n+xx);
        if(find(xx)==find(n+xx) || find(yy)==find(n+yy)){
            cout<<st[i].c;
            return 0;
        }
    }
    cout<<0;
    return 0;
}

by OIER__Tym2011 @ 2024-10-06 15:59:00

@goIdie 已过，太感谢了，已关