MST Kruskal算法（時限）

所以我有一個任務，我能寫代碼和它的作品，但與大的數字，它只是太慢，也許你可以幫助我提高它的時限是3秒。我想聽聽一些想法。在這項任務，我們必須找到最小生成樹。MST Kruskal算法（時限）

輸入將是：

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

來源

2012-05-16 Urs Hofmann Elizondo

嘗試後你的代碼的可讀性的格式成爲可能。這意味着適當的空白使用，清晰的縮進，適當的托架等，這是更容易調試可讀的代碼。 – thagorn

您已經實施了union-find algorithm弄清楚，如果這兩個頂點入射到當前邊屬於同一個組件。但是，你做「聯盟」的方式，

parent[pu]=parent[pv];

可以從元素到根導致線性路徑。防止這種情況的正確方法是將較小的子樹連接到較大的子樹。然而，只是隨機（均勻）決定做任何

parent[pu]=parent[pv];

或

parent[pv]=parent[pu];

應該做的伎倆。

來源

2012-06-12 07:52:40 Dino

MST Kruskal算法（時限）

回答

相關問題