题解 P2126 【Mzc家中的男家丁】

2017-05-19 19:24:02


本题的数据本来有误,感谢管理员的及时更改

本题原本的数据范围对于Kruskal来说很不友好,有很多条边,但感谢管理员将数据范围调小了


一个带并查集的Kruskal,加上读人优化

但在写的时候遇到了一点bug,以为数据中的人是有编号为0的,那么我的并查集的写法就会因为标记的值和0重复了而被卡掉

所以就人为的将每一个编号放大1,然后就A了

不用long long(数据还没有变态到这种地步)


#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#define INF 0x7f7f7f7f
#define maxn 400001
#define max(x,y) x>y?x:y
#define LL long long
using namespace std;
int ans=0;
int f[3000];
struct arr
{
    int x,y,w;
}a[maxn];
inline int read()
{
    int x=0,p=1; char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch == '-') p=-1; ch=getchar();}
    while (ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}
    return x*p;
}
int cmp(arr a,arr b)
{
    return a.w<b.w;
}
int find(int x)
{
    if (!f[x]) return x;
    f[x]=find(f[x]);
    return f[x];
}
int insert(int x,int y)
{
    if (find(x)!=find(y))
    {
        f[find(x)]=find(y);
        return 1;
    }
    return 0;
}
int main()
{
    int n=read(),m=read();

    for (int i=1;i<=m;i++)
    {
        a[i].x=read(),a[i].y=read(),a[i].w=read();
        a[i].x++; a[i].y++;
    }

    sort(a+1,a+m+1,cmp);
    for (int i=1;i<=m;i++)
    {
        if (find(a[i].x)!=find(a[i].y))
        {
            ans+=a[i].w;
            insert(a[i].x,a[i].y);
        }
    }
    printf("%d\n",ans); 
}