社区讨论

求dalao改錯

P1525[NOIP 2010 提高组] 关押罪犯参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi7cvbep
此快照首次捕获于
2025/11/20 19:36
4 个月前
此快照最后确认于
2025/11/20 19:36
4 个月前
查看原帖
CPP
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2e4+5;
const int MAXM=1e5+5;
struct Edge{
    int U,V,W;
}edge[MAXM];
int N,M,Father[MAXN];
int Enemy[MAXN];

inline int Read(){
    int NUMBER=0;
    char CH=0;
    bool FLAG=false;
    while(CH<'0' || CH>'9'){FLAG|=CH=='-';CH=getchar();}
    while('0'<=CH && CH<='9'){NUMBER=(NUMBER<<3)+(NUMBER<<1)+(CH^48);CH=getchar();}
    return FLAG?-NUMBER:NUMBER;
}

bool operator < (Edge TMP1,Edge TMP2){
    return TMP1.W>TMP2.W;
}

inline int Find(int ROOT){
    return Father[ROOT]==ROOT?ROOT:Father[ROOT]=Find(Father[ROOT]);
}

int main(){
    N=Read(); M=Read();
    for(register int I=1;I<=N;I++) Father[I]=I;
    for(register int Edge_Count=1;Edge_Count<=M;Edge_Count++){
        edge[Edge_Count].U=Read();
        edge[Edge_Count].V=Read();
        edge[Edge_Count].W=Read();
    }
    sort(edge+1,edge+M+1);
    for(register int I=1;I<=M+1;I++){
        int U=edge[I].U;
        int V=edge[I].V;
        int W=edge[I].W;
        if(Find(U)==Find(V)){
            printf("%d\n",W); break;
        }
        if(!Enemy[U]) Enemy[U]=V; 
        else Father[Find(Enemy[U])]=Find(V);
        if(!Enemy[V]) Enemy[V]=U;
        else Father[Find(Enemy[V])]=Find(U);
    }
    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...