原题
挺有意思的一道题。
大多数人思路应该是贪心，将犯罪值有大到小排，将两个人放在两个并查集中，如果他们在同一个并查集就退出。这样你画一下样例就明白了，这两个人的确放在两栋楼，但是具体哪个人放在哪栋楼效果是不同的，而你要确定的话又需要枚举一遍，超时妥妥的。
两个互为敌人的位置无法确定，但是很明显还是要用并查集的。
敌人的敌人呢？他们是不是一定在同一栋楼？（贪心思想）
所以每次可以确定在一个并查集的是敌人的敌人，如果一个人没有敌人，这个人就没有用了。当敌人的敌人有矛盾时，就是最优解。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iomanip> using namespace std; int n,m,father[40009];bool vis[20009]; struct node{ int l,r,data; }a[100007]; int cmp(node a,node b) { return a.data>b.data; } int find(int x) { if(father[x]==x) return x; return father[x]=find(father[x]); } int main() { cin>>n>>m; for(int i=1;i<=n*2;++i) father[i]=i; for(int i=1;i<=m;++i) cin>>a[i].l>>a[i].r>>a[i].data; sort(a+1,a+m+1,cmp); for(int i=1;i<=m;++i) { if(find(a[i].l)==find(a[i].r)) { cout<<a[i].data; return 0; } else { int fx=find(a[i].l),fy=find(a[i].r); father[fx]=find(a[i].r+n); father[fy]=find(a[i].l+n); } } cout<<"0"; return 0; }
