FZu Problem 2233 ~APTX4869 (并查集 + sort)

题目链接：

题目描述：

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

解题思路：

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

 #include <cstdio>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define lson 2*root

 #define rson 2*root+1

 typedef __int64 LL;

 const LL mod = ;

 const LL INF= 1e9+;

 const int maxn = ;

 struct node

 {

     int x, y, z;

 }a[maxn*maxn];

 int vis[maxn];

 bool cmp (node a, node b)

 {

     return a.z < b.z;

 }

 void init ()

 {

     for (int i=; i<maxn; i++)

         vis[i] = i;

 }

 int find (int x)

 {

     if (vis[x] != x)

         vis[x] = find(vis[x]);

     return vis[x];

 }

 int main ()

 {

     int n;

     while (scanf ("%d", &n) != EOF)

     {

         init ();

         int m = ;

         for (int i=; i<n; i++)

             for (int j=; j<n; j++)

             {

                 scanf ("%d", &a[m].z);

                 if (i < j)

                  {

                     a[m].x = i;

                     a[m ++].y = j;

                  }

             }

         sort (a, a+m, cmp);

         int ans = INF, cnt = n;

         for (int i=; i<m; i++)

         {

             int x = find (a[i].x);

             int y = find (a[i].y);

             if (x == y)

                 continue;

             if (x != y && cnt > )

             {

                 vis[x] = y;

                 cnt --;

             }

             else

                 ans = min (ans, a[i].z);

             if (ans != INF)

                 break;

         }

         printf ("%d\n", ans);

     }

     return ;

 }

 /*

 4

 -1 100 200 300

 100 -1 400 500

 200 400 -1 600

 300 500 600 -1

 */

巴特西

FZu Problem 2233 ~APTX4869 (并查集 + sort)

最新文章

热门文章