CodeForces

Luogu

题意

因为Luogu上那个翻译过于晦涩,所以附上一份䕀来的翻译:

有 $N$ 个王子和个 $M$ 个公主,每个公主或王子都只能选择至多一个王子或公主作为自己的结婚对象(王子选择公主,公主选择王子)。每个公主有且仅有两个中意的王子 $a,b$ ,她只会至多选择其中一个作为自己的结婚对象,而如果某个公主选择了自己的结婚对象,就会给出 $w$ 的嫁妆。求在满足所有公主的条件的情况下能够给出的最大嫁妆。$N,M\leq 2×10^5,w\leq 10^4$ 。

分析

显然可以上 $\mathrm{KM}$ ,但是会 $T$ 。

正解比较神仙。

将每个公主中意的两个王子 $u$ 和 $v$ 之间连一条边,边权为对应的嫁妆数。

那么我们就是要求出这个图的最大生成基环森林。

考虑魔改 $\mathrm{Kruskal}$ 。并查集维护一下集合中环的个数,然后合并时分类讨论一下即可。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

struct Edge { int u,v,w; } e[N];
inline int cmp(Edge a,Edge b) { return a.w>b.w; }

int f[N],c[N];

inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=n;++i) f[i]=i,c[i]=0;
    for (re int i=1;i<=m;++i) e[i]=(Edge){read(),read(),read()};
    sort(e+1,e+m+1,cmp);
    int ans=0;
    for (re int i=1;i<=m;++i) {
        int p=find(e[i].u),q=find(e[i].v);
        if (p!=q&&(c[p]+c[q]<2)) f[q]=p,c[p]|=c[q],ans+=e[i].w;
        else if (p==q&&!c[p]) c[p]=1,ans+=e[i].w;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 10 PM