Codeforces 875F - Royal Question

题目: Codeforces 875F - Royal Questions

翻译

有 n 个王子和 m 个公主，每个公主有两个中意的王子，公主嫁出去的嫁妆是 w。一个王子最多能娶一个公主，一个公主最多能娶一个王子，可以不让所有的公主和王子结婚。求最大嫁妆总数。

分析

因为是搜索并查集找到的题目，所以主观就向并查集想了。

把公主看中的两个王子合到一个集合内，有两种情况。

1. 集合内王子的数量大于等于公主数量，也就是集合内没有环或者重复的边。此时这个集合内所有公主的嫁妆都可以得到。

2. 集合内王子的数量小于公主数量，此时，集合内可得到嫁妆的个数等于王子的个数，需要贪心，也就是从大到小取嫁妆值得和。

因为第二种情况的存在，需要先把公主中意的王子和嫁妆按照嫁妆的大小逆序排列，这样保证，当出现王子数量小于公主数量的情况时，就抛弃新的嫁妆，因为新的嫁妆一定小于等于之前的任何一个嫁妆。

最后把每个根的总和累加

代码(C++)

我程序的 Accepted 截图

//
//  main.cpp
//  ACM
//
//  Created by Tconan on 2017/11/8.
//  Copyright © 2017年 Tconan. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int total[200010];
int root[200010];
int pairs[200010];

int getRoot(int i) {
    if (root[i] != i) {
        root[i] = getRoot(root[i]);
        return root[i];
    }
    return i;
}

void merge(int left, int right, int value) {
    left = getRoot(left);
    right = getRoot(right);
    
    if (left == right) {
        if (pairs[left] < 0) {
            total[left] += value;
        }
        pairs[left] = min(1, pairs[left] + 1);
        return;
    }
    
    total[left] += total[right];
    if (pairs[left] < 0 || pairs[right] < 0) {
        total[left] += value;
    }
    pairs[left] += min(1, pairs[right] + 1);
    
    root[right] = left;
}

struct Point {
    int a;
    int b;
    int w;
};

bool complare(Point left, Point right) {
    return left.w > right.w;
}

int main(int argc, const char * argv[]) {
    
    int n, m, sum = 0;
    cin>>n>>m;
    
    for (int i=0; i<=n; ++i) {
        total[i] = 0;
        root[i] = i;
        pairs[i] = -1;
    }
    
    // 开始这个地方写写成了10010，结果报错的信息是 “Time limit exceeded on test 15”
    // 找了半天才发现，改成200010就AC了
    Point points[200010];
    
    int a, b, w;
    for (int i=0; i<m; ++i) {
        cin>>a>>b>>w;
        points[i].a = a;
        points[i].b = b;
        points[i].w = w;
    }
    
    sort(points, points + m, complare);
    
    for (int i=0; i<m; ++i) {
        merge(points[i].a, points[i].b, points[i].w);
    }
    
    for (int i=1; i<=n; ++i) {
        if (root[i] == i) {
            sum += total[i];
        }
    }
    
    cout<<sum<<endl;
    
    return 0;
}