水了这么多题，总算有一道绿题能看了。。
首先由分析输入输出数据可以想到进行离线并查集，因为带有权值（不是带权并查集），故先将结构体根据权值由大到小排序，在做合并操作，若发现合并后又摩擦发生，则立刻输出并结束程序（因为答案为最大的单个摩擦事件）
那个该如何建立并查集呢？为了让更多摩擦事件不发生，或是尽量让权值小的摩擦事件发生，我们应尽量将权值大的摩擦事件双方放在两个不同的集合中，用b记录是否有第一个人的敌方已经进入另一个并查集，若已存在，则将新的敌方与之前的放入同一集合，反之记录第一个人已有敌方存在，并放入与第一个人不同的集合中，下面为实现代码：
1 #include<set> 2 #include<map> 3 #include<list> 4 #include<queue> 5 #include<stack> 6 #include<string> 7 #include<cmath> 8 #include<ctime> 9 #include<vector> 10 #include<bitset> 11 #include<memory> 12 #include<utility> 13 #include<cstdio> 14 #include<sstream> 15 #include<iostream> 16 #include<cstdlib> 17 #include<cstring> 18 #include<algorithm> 19 using namespace std; 20 21 int n,m; 22 int a[200005],b[200005]; 23 struct node{ 24 int id1,id2,val; 25 }zy[200005]; 26 27 bool cmp(node a,node b){//结构体排序 28 return a.val>b.val; 29 } 30 31 int find(int z){//查找该集合的代表元 32 if(z==a[z]){ 33 return z; 34 } 35 return a[z]=find(a[z]); 36 } 37 38 int main(){ 39 scanf("%d%d",&n,&m); 40 for(int i=1;i<=n;i++){ 41 a[i]=i; 42 } 43 for(int i=1;i<=m;i++){ 44 scanf("%d%d%d",&zy[i].id1,&zy[i].id2,&zy[i].val);//读入 45 } 46 sort(zy+1,zy+1+m,cmp);//以权值为关键字排序 47 for(int i=1;i<=m;i++){ 48 if(find(a[zy[i].id1])==find(a[zy[i].id2])){//若已有摩擦事件发生，则输出 49 printf("%d ",zy[i].val); 50 return 0; 51 } 52 if(!b[zy[i].id1]){//52~63行为核心代码，具体在上文已经提到了，望各位理解 53 b[zy[i].id1]=zy[i].id2; 54 } 55 else{ 56 a[find(zy[i].id2)]=find(b[zy[i].id1]); 57 } 58 if(!b[zy[i].id2]){ 59 b[zy[i].id2]=zy[i].id1; 60 } 61 else{ 62 a[find(zy[i].id1)]=find(b[zy[i].id2]); 63 } 64 } 65 printf("0 ");//若在前面的程序中无输出，则输出0 66 return 0; 67 }
我真的想说，还是难题做的爽啊，做好了之后真的很舒服。。。