啊啊,有没有人救救我呀QwQ
by Merci @ 2019-02-21 21:35:46
@[sam上帝](/space/show?uid=122822) 这里
```cpp
#include<cstdio>
#include<algorithm>
inline int in();
inline void wr(int);
const int N=(int)2e4+5,M=(int)1e5+5;
struct Node{
int a,b,c;
}s[M];
inline bool cmp(Node,Node);
int f[N],kill[N];
//kill[i]表示第i名罪犯的敌人的编号,
//由于先前s[]数组是排好序的,故此数
//组默认是仇恨最大的敌人,仇恨小的不保存。
//特别地,初始状态没有敌人标记为0.
inline int fa(int);
int main(int argc,char**argv){
register int n=in(),m=in();
for(register int i=1;i<=m;++i)
s[i]=(Node){in(),in(),in()};
std::sort(s+1,s+1+m,cmp);
for(register int i=1;i<=n;++i)
f[i]=i;//自己是自己的集合代表
for(register int i=1;i<=m;++i){
register int x=s[i].a,y=s[i].b;
//先赋值,方便后面的处理。
if(fa(x)==fa(y)){wr(s[i].c);return 0;}
//如果根据前面的安排这两名罪犯必须被安排在一起,
//(否则会引起更大的事故[冲突事件]),还不如引起这场。
//所以直接输出答案。
if(!kill[x])kill[x]=y;
//如果这两个人的集合代表(监狱代表)没仇,那么现在有仇了。
else f[fa(kill[x])]=fa(y);
//关键!由于只有两个监狱,所以如果x这个人又跟更大的仇人有仇,
//又跟当前的仇人y有仇,那就把两个仇人安排在同一监狱里,
//尽可能避免先被处理的冲突(影响力大的冲突)
if(!kill[y])kill[y]=x;
//现在有仇了。
else f[fa(kill[y])]=fa(x);
//这里简单:反过来再跑一遍
}
wr(0);//都没仇输出0
}
inline int in(){
register char c=getchar();
register int x=0,f=1;
for(;c<'0'||c>'9';c=getchar())
if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c&15);
return x*f;
}
inline void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x/10)wr(x/10);
putchar(x%10+'0');
}
inline bool cmp(Node a,Node b){
return a.c>b.c;
}
inline int fa(int x){
return x==f[x]?x:fa(f[x]);
}
```
代码我明天看。今天实在没时间。不好意思啦~
by 言琢დ @ 2019-02-22 00:07:19
自己刚写的,**注意“判断”不要查找祖先,“合并”要查找祖先**。
by 言琢დ @ 2019-02-22 00:07:46
刚看了你的代码
@[sam上帝](/space/show?uid=122822)
觉得逻辑是有点问题的,故不知道60pts是如何获得的, https://www.luogu.org/paste/dh6jdlhm
新的代码在这里,**没有帮你修改**,只是给你提出一点建议,**需要修改的地方都给你指出来了**,所以希望你自己修改好这份代码,下次再遇到类似的题目就不会再犯错了。最后,强调两点:
1. 这题不是**带权并查集**。
2. **判断**不要查找祖先,**合并**要查找祖先。
by 言琢დ @ 2019-02-22 21:27:37
@[霸鲁巴托斯](/space/show?uid=50606) 然而这题可以用带权并查集
by 祥瑞御免 @ 2019-07-20 10:10:39