Highways

POJ-1751

注意这里的样例答案也是对的，只是输出顺序改变，但是这也没关系，因为题目加了特殊判断。

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdio>

#include<cmath>

using namespace std;

const int maxn=755;

const int maxm=500004;

int n,m;

int e;

int x[maxn];

int y[maxn];

int set[maxn];

struct node{

    int from;

    int to;

    double cost;

    bool operator<(const node& t)const{

        return cost<t.cost;

    }

};

node edges[maxm];

int find(int x){

    return x==set[x]?set[x]:set[x]=find(set[x]);

}

void kruskal(){

    sort(edges,edges+e);

    for(int i=0;i<e;i++){

        int x=edges[i].from;

        int y=edges[i].to;

        double cost=edges[i].cost;

        int from=find(x);

        int to=find(y);

        if(from!=to){

            set[from]=to;

            cout<<x<<" "<<y<<endl;

        }

    }

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    while(cin>>n){

        e=0;

        for(int i=1;i<=n;i++){

            cin>>x[i]>>y[i];

            set[i]=i;

            for(int j=1;j<i;j++){

                double cost=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

                edges[e++]=node({i,j,cost});

            }

        }

        cin>>m;

        for(int i=0;i<m;i++){

            int a,b;

            cin>>a>>b;

            int a1=find(a);

            int b1=find(b);

            if(a1!=b1)

                set[a1]=b1;

        }

        kruskal();

    }

    return 0;

}

巴特西

POJ-1751(kruskal算法)

Highways

POJ-1751

最新文章

热门文章