这道题看了网上好多的题解，用的都是二分图的算法，但是自己却用的是贪心加并查集的做法。二分图的做法其实我并不会，是不是很神奇。
实际上贪心的算法很好想，只要先用一个结构体维护两个人的怒气值，然后从小到大排序。再从小到大搜一遍。时间复杂度大概是（nlogn+n）总时154ms，基本上是C++中最快的了。。。。
在搜的过程中，就需要用到并查集了。因为需要尽量把不会产生怨气值的罪犯关在一起，所以首先维护一个名为fa的数组，记录的是两个监狱中所关押的犯人，在从小往大搜的过程中，假设是第i条关系，如果这条关系所连接的两个人已经被关在同一个监狱中则为矛盾，输出怨气值即可，如果两个人不在同一个监狱，那么则进行下一步。下一步需要用到另一个数组dui，即“敌对”。假设第i条关系连接的两个
人是a和b，那么就需要将a和b关在两个监狱中，该如何表示呢？就利用到了dui这个数组。dui[a] 表示会和 a 产生怒气值的罪犯的编号。因为这个人此前肯定已经在与 a 不同的监狱中，所以就将当前，即 b 这个罪犯和dui[a]关在一起。同理，将a和dui[b]关在一起。这样这道题就解决了。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct node{ int u,v,c; } a[600001]; int n,m,fa[1000000]; int com(node a,node b)//比较函数 { return a.c>b.c; } int find(int x) { if(fa[x]!=x) fa[x]=find(fa[x]);//路径压缩 return fa[x]; } void cling(int x,int y) { int f1=find(x),f2=find(y); if(f1!=f2) fa[f1]=f2; } int dui[1000000];//敌对 int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c); sort(a+1,a+m+1,com); for(int i=1;i<=m;i++) fa[i]=i;//初始化 for(int i=1;i<=m;i++){ int f1=find(a[i].u),f2=find(a[i].v); if(f1==f2){//如果矛盾则输出答案 cout<<a[i].c; return 0; } if(dui[a[i].u]==0) dui[a[i].u]=a[i].v;//如果没有敌对的罪犯，直接将当前罪犯添加为敌对 if(dui[a[i].v]==0) dui[a[i].v]=a[i].u;//同理 cling(dui[a[i].u],a[i].v);//将u的敌对罪犯与v关在一起 cling(dui[a[i].v],a[i].u);//同理 } cout<<"0";//如果始终不矛盾，则为0 }