家园重建 (HGOI 2019.2.17 T3)

2019-02-17 15:28:27


题目大意

给出n个点,m条边,每条边有自己的权值

这个图只可以被分成若干棵树,每棵树上都可以有一个环,问怎样连边使得权值和最大

数据范围

n<=300

解法

很简单,就是一个贪心。按最大生成树去做就可以。

但是要注意,要标记一下一棵树中已经有没有环了。假如一条边链接的两棵树都已经有环了,那么这条边就不能加了。如果一条边链接同一棵树的两点,那么已经有环了也不能连了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int n,m,ans=0;
int fa[310],f[310];
struct Edge
{
    int x,y,z;
}e[101000];
bool cmp(Edge a,Edge b) {return a.z>b.z;}
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].z);
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x=e[i].x,y=e[i].y;
        int fx=find(x),fy=find(y);
        if(fx==fy && !f[fx]) ans+=e[i].z,f[fx]=1;
        else if(fx!=fy && (!f[fx] || !f[fy]))
        {
            ans+=e[i].z;
            if(!f[fx] && !f[fy]) fa[fx]=fy;
            else if(f[fx]) fa[fy]=fx;
            else fa[fx]=fy;
        }
    }
    printf("%lld",ans);
    return 0;
}