justoj connect(边的处理)

CONNECT

https://oj.ismdeep.com/contest/problem?id=1702&pid=2

Problem Description

Input

第一行输入一个整数n (1≤n≤2∗105)n (1≤n≤2∗105)

接下来nn行，第ii行包含33个整数XiXi，YiYi和ZiZi(|Xi|,|Yi|,|Zi|≤109)(|Xi|,|Yi|,|Zi|≤109),代表第ii个点的坐标，数据保证不会有任意两个点的坐标相同

Output

输出最小代价

Sample Input

Sample Output

思路：本质是最小生成树。需要对边进行处理。

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 200000 + 5;

struct Edge

{

    ll u,v,dis;

};

struct Point

{

    ll x,y,z,index;

};

Edge edge[maxn*3];

Point point[maxn];

int fa[maxn];

ll edgenum;

ll res;

bool cmpx(Point a,Point b)

{

    return a.x<b.x;

}

bool cmpy(Point a,Point b)

{

    return a.y<b.y;

}

bool cmpz(Point a,Point b)

{

    return a.z<b.z;

}

bool cmpdis(Edge a,Edge b)

{

    return a.dis<b.dis;

}

int find(int x)

{

    while(x!=fa[x])

    x=fa[x]=fa[fa[x]];

    return x;

}

int main()

{

    ll n;

    scanf("%lld",&n);

    for(int i=0;i<n;i++)

    {

        scanf("%lld%lld%lld",&point[i].x,&point[i].y,&point[i].z);

        point[i].index=i;

    }

    edgenum=0;

    sort(point,point+n,cmpx);

    for(int i=0;i<n-1;i++)

    {

        edge[edgenum].u=point[i+1].index;

        edge[edgenum].v=point[i].index;

        edge[edgenum].dis=point[i+1].x-point[i].x;

        edgenum++;

    }

    sort(point,point+n,cmpy);

    for(int i=0;i<n-1;i++)

    {

        edge[edgenum].u=point[i+1].index;

        edge[edgenum].v=point[i].index;

        edge[edgenum].dis=point[i+1].y-point[i].y;

        edgenum++;

    }

    sort(point,point+n,cmpz);

    for(int i=0;i<n-1;i++)

    {

        edge[edgenum].u=point[i+1].index;

        edge[edgenum].v=point[i].index;

        edge[edgenum].dis=point[i+1].z-point[i].z;

        edgenum++;

    }

    sort(edge,edge+edgenum,cmpdis); //把每条边从小到大排

    for(int i=0;i<n;i++)

    fa[i]=i;

    int eu,ev,cnt=0;

    for(int i=0;i<edgenum;i++)

    {

        eu=find(edge[i].u);

        ev=find(edge[i].v);

        if(eu!=ev){

        fa[ev]=eu;

        res+=edge[i].dis;

        cnt++;

        }

        if(cnt==n-1) break;

    }

    printf("%lld\n",res);

    return 0;

}

巴特西

justoj connect(边的处理)

CONNECT

Problem Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章