社区讨论
求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 条回复,欢迎继续交流。
正在加载回复...