1

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

输入将是：

  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;                                       
}
4

1 回答 1

0

您已经实现了一个联合查找算法来确定与当前边相连的两个顶点是否属于同一个组件。然而，你做“联合”的方式，

parent[pu]=parent[pv];

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

parent[pu]=parent[pv];

或者

parent[pv]=parent[pu];

应该做的伎俩。

于 2012-06-12T07:52:40.500 回答