题目链接：
题目描述：
给一个n*n的矩阵，(i, j)表示第 i 种材料 和 第 j 种材料的影响值，这个矩阵代表这n个物品之间的影响值。当把这n个物品分成两部分后，每部分内部材料不会相互影响，但是不同部分的材料之间会相互影响。问如何分割使得两部分材料相互之间的最小影响值最大？
解题思路：
材料内部不会影响，那么只需要把影响值小的物品放在同一部分即可，所以用结构体保存物品之间的影响值，然后sort一下，影响值小的物品用并查集放在一个集合，当集合等于2的时候，遍历到物品分别在不同集合的影响值就是ans。
1 #include <cstdio> 2 #include <queue> 3 #include <stack> 4 #include <cmath> 5 #include <cstring> 6 #include <iostream> 7 #include <algorithm> 8 using namespace std; 9 10 #define lson 2*root 11 #define rson 2*root+1 12 typedef __int64 LL; 13 const LL mod = 1000000007; 14 const LL INF= 1e9+7; 15 const int maxn = 810; 16 17 struct node 18 { 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<maxn; i++) 30 vis[i] = i; 31 } 32 33 int find (int x) 34 { 35 if (vis[x] != x) 36 vis[x] = find(vis[x]); 37 return vis[x]; 38 } 39 int main () 40 { 41 int n; 42 while (scanf ("%d", &n) != EOF) 43 { 44 init (); 45 int m = 0; 46 for (int i=0; i<n; i++) 47 for (int j=0; j<n; j++) 48 { 49 scanf ("%d", &a[m].z); 50 if (i < j) 51 { 52 a[m].x = i; 53 a[m ++].y = j; 54 } 55 } 56 sort (a, a+m, cmp); 57 58 int ans = INF, cnt = n; 59 for (int i=0; i<m; i++) 60 { 61 int x = find (a[i].x); 62 int y = find (a[i].y); 63 64 if (x == y) 65 continue; 66 67 if (x != y && cnt > 2) 68 { 69 vis[x] = y; 70 cnt --; 71 } 72 else 73 ans = min (ans, a[i].z); 74 75 if (ans != INF) 76 break; 77 } 78 79 printf ("%d ", ans); 80 } 81 return 0; 82 } 83 84 /* 85 4 86 -1 100 200 300 87 100 -1 400 500 88 200 400 -1 600 89 300 500 600 -1 90 */