题目链接：

　　

题目描述：

　　给一个n*n的矩阵，(i, j)表示第 i 种材料 和 第 j 种材料的影响值，这个矩阵代表这n个物品之间的影响值。当把这n个物品分成两部分后，每部分内部材料不会相互影响，但是不同部分的材料之间会相互影响。问如何分割使得两部分材料相互之间的最小影响值最大？

解题思路：

　　材料内部不会影响，那么只需要把影响值小的物品放在同一部分即可，所以用结构体保存物品之间的影响值，然后sort一下，影响值小的物品用并查集放在一个集合，当集合等于2的时候，遍历到物品分别在不同集合的影响值就是ans。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 using namespace std; 9 10 #define lson 2*root11 #define rson 2*root+112 typedef __int64 LL;13 const LL mod = 1000000007;14 const LL INF= 1e9+7;15 const int maxn = 810;16 17 struct node18 {19 int x, y, z;20 }a[maxn*maxn];21 int vis[maxn];22 bool cmp (node a, node b)23 {24 return a.z < b.z;25 }26 27 void init ()28 {29 for (int i=0; i
            
              2)68 {69 vis[x] = y;70 cnt --;71 }72 else73 ans = min (ans, a[i].z);74 75 if (ans != INF)76 break;77 }78 79 printf ("%d\n", ans);80 }81 return 0;82 }83 84 /*85 486 -1 100 200 30087 100 -1 400 50088 200 400 -1 60089 300 500 600 -190 */