Codeforces875 F-神奇图论

Codeforces875 F-Royal Questions
传送门
题意：
n个王子，m个公主，给出第i个公主可以嫁给的两个王子ai,bi以及嫁妆，每个王子只能娶一个公主，公主只能在两个中选一个，求最大嫁妆。

Solution：
这题乍一看是一个二分图匹配，但是思考良久发现不可做，于是决定转化思路，首先想到了贪心：首先按照嫁妆把这m组数排序，然后贪心的去搞，但是怎么判断具体嫁给那一个王子呢？一个很妙的想法：对于每个公主i，把ai和bi连边，表示选择ai或者bi，这样操作后我们可以发现：如果形成了的联通块中点数大于等于边数，那么那么这个方案是可行的，因为每一个边表示一种选择，每一个点表示王子，一定会有一种合法方案使得王子不被重复选，同理，如果点数小于边数，那么这个方案就不合法。
于是这个题就转化成了这样一个问题：不停的加边使得每个联通块只有一个环，最大化边权和。用并查集即可解决。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int n,m;
struct E{
    int x,y,v;
}e[200010];
long long ans;
int f[200010];
bool p[200010];
bool cmp(E a,E b)
{
    return a.v>b.v;
}
int find(int x)
{
    if (x!=f[x]) f[x]=find(f[x]);
    return f[x];
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v);
    for (int i=1;i<=n;i++)
        f[i]=i;
    sort(e+1,e+1+m,cmp);
    for (int i=1;i<=m;i++)
    {
        int x=find(e[i].x);
        int y=find(e[i].y);
        if (x!=y)
        {
            if (p[x]&&p[y]) continue;
            p[x]=p[x]|p[y];
            ans+=e[i].v;
            f[y]=x;
        }
        else if (!p[x]) ans+=e[i].v,p[x]=1;
    }
    printf("%lld",ans);
}