题目
https://www.luogu.org/problemnew/show/P1525
思路
- 把所有边sort一遍从大到小排列
- 运用并查集思想敌人的敌人就是朋友
- 从最大边开始查找连着的两个罪犯
- 如果他们在一个*就输出并结束程序
- 如果不在就把他们互为敌人存下来
- 如果他们已经有一个敌人了那就把他们敌人和自己合并(因为总共只有两个*)
- 最后判0
代码
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,tot;
int fat[400010];
struct edge
{
int l,r,w;
}e[400010];//左边的点 右边的点 仇恨值
bool cmp(edge a,edge b)
{
return a.w>b.w;
}//按照仇恨值从大到小
int enemy[400010];//存敌人
int find(int x)
{
if(x!=fat[x])
fat[x]=find(fat[x]);
return fat[x];
}
void unionn(int a,int b)
{
int fa=find(a);
int fb=find(b);
fat[fa]=fb;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
fat[i]=i;
for(int i=1;i<=m;i++)
cin>>e[i].l>>e[i].r>>e[i].w;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++)
{
if(find(e[i].l)==find(e[i].r))//如果在同一*就输出并结束
{
cout<<e[i].w;
return 0;
}
else
{
if(!enemy[e[i].l])//如果左边的点没有敌人 就加入敌人
enemy[e[i].l]=e[i].r;
else//如果有敌人 就合并敌人和右边的点
unionn(enemy[e[i].l],e[i].r);
if(!enemy[e[i].r])//同上
enemy[e[i].r]=e[i].l;
else
unionn(e[i].l,enemy[e[i].r]);
}
}
cout<<0;//特判0
}