题目
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
}
转载于:https://www.cnblogs.com/BrokenString/p/9279515.html
