c++ - MST Kruskal 算法(时间限制)

Question

所以我有一个任务，我能够编写一个代码并且它可以工作，但是对于大数字来说它太慢了，也许你可以帮助我改进它，时间限制是 3 秒。我想听听一些想法。在这个作业中，我们必须找到最小生成树。

输入将是:

  1. number of testcases,
  2. number of nodes,
  3. a number that says how long can tha longest edge be,
  4. all the coordinates of the nodes

那么输出应该是最小值。 MST 的距离，如果没有 MST，则输出应为 -1。

举个例子:

  Input:
    1     //number of testcases
    6 5   //number of nodes, max. length of an edge
    3 6   //x-,y-coordinates
    4 7
    8 1
    4 4
    2 7
    3 3

  Output:
  11

代码如下:

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<deque>
#include<vector>
#include<cmath>
#include<cstdlib>

using namespace std;

#define edge pair<int,int>//format (w,(u,v))
                          //(weights, (node,node))
deque<pair<double,edge> > G,MST;
deque<int> parent(1000);
int N,E,diff;
int total;
double sum;
deque<int> X,Y;

int findset(int x,deque<int>parent){
    if(x!=parent[x])
        parent[x]=findset(parent[x],parent);
    return parent[x];                    
}                                                                    

int Kruskal(){
    for(int i1=0;i1<N;i1++){ //calculate  distance between each node
        for(int j1=i1;j1<N;j1++){
            int A,B;
            double C;
            A=((X[i1]-X[j1])*(X[i1]-X[j1])); 
            B=((Y[i1]-Y[j1])*(Y[i1]-Y[j1]));
            C=sqrt(A+B);
            G.push_back(pair<double,edge>(C,edge(i1,j1)));
         }
    }

    E=G.size();//how many edges
    int i,pu,pv;
    sum=0;
    stable_sort(G.begin(),G.end());  
    for (i=total=0;i<E;i++){
        pu=findset(G[i].second.first, parent);
        pv=findset(G[i].second.second, parent);
        if(pu!=pv){
            MST.push_back(G[i]);
            total+=G[i].first;
            sum+=G[i].first;

            if(G[i].first>diff)
                return -1;
            parent[pu]=parent[pv];
        }
    }
    return 0;
}  

int main(){
    int t,nodes;
    double w;
    diff=0;
    for(cin>>t ; t>0 ; t--){
        N=0;
        diff=0;
        X.clear();
        Y.clear();
        MST.clear();
        G.clear();
        X.resize(0);
        Y.resize(0);

        cin>>N; //how many nodes
        for(int i=0; i<N; i++)
            parent[i]=i;
        cin>>diff;
        nodes=N;

        for(nodes; nodes>0;nodes--){        //coordinates of nodes
            int x,y;
            cin>>x;
            X.push_back(x); 
            cin>>y;
            Y.push_back(y);
        }

        int a=0;
        if(Kruskal()==0){
            a=sum;
            cout<<a<<endl;
        }
        else
            cout<<-1<<endl;           
    }
    system("pause");
    return 0;                                       
}

Answer 1

您已经实现了一个 union-find algorithm判断入射到当前边的两个顶点是否属于同一组件。然而，你做“union ”的方式，

parent[pu]=parent[pv];

可能导致从元素到根的线性路径。防止这种情况的正确方法是将较小的子树附加到较大的子树。然而，只是随机地(一致地)决定做任何一个

parent[pu]=parent[pv];

或

parent[pv]=parent[pu];

应该可以解决问题。