（并查集）~APTX4869（fzu 2233）

http://acm.fzu.edu.cn/problem.php?pid=2233

Problem Description

为了帮助柯南回到一米七四，阿笠博士夜以继日地研究APTX4869的解药。他得出了如下结果：

1.解药由n种原料构成；

2.对于两种不同的的原料a,b，它们之间有个影响值f(a,b)；

3.需要把原料分成两个部分X,Y，每部分中至少有一种原料；

4.解药的效果由分别属于X,Y的原料之间，最小的影响值决定，即

效果=min{f(a,b)|a∈X,b∈Y)}

博士需要你帮忙求出：在所有的方案中，最大的效果值可以是多少？

Input

多组数据(<=10)，处理到EOF。

每组数据输入第一行为一个正整数n。

接下去是一个n行n列的整数矩阵，同一行的数以空格隔开。矩阵第i行j列表示第i种和第j种材料的影响值f(i,j)。给出的矩阵是对称的，即f(i,j)=f(j,i)。当i=j时，f(i,i)没有意义，矩阵该处的值为-1。

2<=n<=800。当i!=j时，0<=f(i,j)<=1000000；当i=j时，f(i,j)=-1。

Output

每组数据输出一行，表示最大可能的效果值。

Sample Input

3 -1 100 300 100 -1 200 300 200 -1

Sample Output

200

Source

福州大学第十三届程序设计竞赛

题目描述：

　　给一个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 long long LL;

const LL mod = ;

const LL INF= 1e9+;

const int N = ;

struct node

{

    int x, y, cost;

    bool friend operator < (node n1, node n2)

    {

        return n1.cost < n2.cost;

    }

}a[N*N];

int f[N];

int Find(int x)

{

    if(f[x]!=x)

        f[x] = Find(f[x]);

    return f[x];

}

int main()

{

    int n;

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

    {

        int i, j, k=;

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

            f[i] = i;

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

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

        {

            scanf("%d", &a[k].cost);

            if(i<j)

            {

                a[k].x = i;

                a[k++].y = j;

            }

        }

        sort(a, a+k);

        int ans = INF, cnt=n;

        for(i=; i<k; i++)

        {

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

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

            if(x==y) continue;

            if(x!=y && cnt>)

            {

                f[x] = y;

                cnt--;

            }

            else

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

            if(ans!=INF) break;

        }

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

    }

    return ;

}

秒客网