我的博客

codevs 1069 关押罪犯

目录
  1. 输入描述 Input Description
  2. 输出描述 Output Description
  3. 样例输入 Sample Input
  4. 样例输出 Sample Output
  5. 数据范围及提示 Data Size & Hint
  • 题解
  • 题目描述 Description

    S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c 的冲突事件。
    每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。
    在详细考察了N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。那么,应如何分配罪犯,才能使Z 市长看到的那个冲突事件的影响力最小?这个最小值是少?

    输入描述 Input Description

    第一行为两个正整数N 和M,分别表示罪犯的数目以及存在仇恨的罪犯对数。

    接下来的M 行每行为三个正整数aj,bj,cj,表示aj 号和bj 号罪犯之间存在仇恨,其怨气值为cj。数据保证且每对罪犯组合只出现一次。

    输出描述 Output Description

    共1 行,为Z 市长看到的那个冲突事件的影响力。如果本年内监狱

    中未发生任何冲突事件,请输出0。

    样例输入 Sample Input

    4 6

    1 4 2534

    2 3 3512

    1 2 28351

    1 3 6618

    2 4 1805

    3 4 12884

    样例输出 Sample Output

    3512

    数据范围及提示 Data Size & Hint

    罪犯之间的怨气值如下面左图所示,右图所示为罪犯的分配方法,市长看到的冲突事件影响力是3512(由2 号和3 号罪犯引发)。其他任何分法都不会比这个分法更优。

    【数据范围】

    对于30%的数据有N≤ 15。

    对于70%的数据有N≤ 2000,M≤ 50000。

    对于100%的数据有N≤ 20000,M≤ 100000。

    题解

    对于 n 个点,这里使用了长度为 n * 2 的 fa 数组。例如当 n = 4 时。

    1234567812345678

    黑色数字时数组下标,白字时数组内容。

    对于例子:

    4 3
    1 2 9
    1 3 8
    2 3 7

    首先读入数据,并按照仇恨值从大到小排序。
    从仇恨值最大的 1 2 9 开始。
    看 1 2 是否再同一个集合中,如果再则输出这时的仇恨值 9。
    如果不再则执行:

    1
    2
    fa[getfa(ps[i].x+n)] = getfa(ps[i].y);
    fa[getfa(ps[i].y+n)] = getfa(ps[i].x);

    就是

    1234567812342178

    下标 5 (就是 x + n)变成了 2,下标 6 变成了 1。

    再看 1 3 8
    1 3 再不同集合
    在执行并集操作

    1234567813345628

    这次把下标 3 变成了 3,下标 7 变成了 2。

    再看 2 3 7
    这是 2 和 3 再同一个集合内,说明 2 和 3 不可避免的会分到一个监狱,所以输出最大仇恨值 7。

    AC 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    #include <iostream>
    #include <algorithm>
    using namespace std;

    const int maxn = 20004, maxm = 100005;
    int fa[maxn<<1];

    struct p {
    int x, y, v;
    }ps[maxm];

    bool operator < (const p &a, const p &b) {
    return a.v > b.v;
    }

    int getfa(int x) {
    return fa[x] == x? x : fa[x]=getfa(fa[x]);
    }

    int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    cin >> ps[i].x >> ps[i].y >> ps[i].v;
    for (int i = 1; i <= n<<1; i++) fa[i] = i;
    sort(ps, ps+m);
    for (int i = 0; i < m; i++) {
    if (getfa(ps[i].x) == getfa(ps[i].y)) {
    cout << ps[i].v << endl;
    return 0;
    }
    fa[getfa(ps[i].x+n)] = getfa(ps[i].y);
    fa[getfa(ps[i].y+n)] = getfa(ps[i].x);
    }
    cout << 0 << endl;
    }

    评论无需登录,可以匿名,欢迎评论!