克鲁斯卡 （clsk） 求最小生成树.txt

克鲁斯卡 （Clsk） 求最小生成树

#include <iostream>      // 克鲁斯卡 （Clsk） 求最小生成树。l[n]为无向图各个 
边的信息。 
#include <algorithm>     // n为顶点数，m为边数，函数clsk()返回最小代价值。 
#include <fstream>       // 坐标一律以 0 开始。 
#include <deque> 
using namespace std; 
ifstream fin("clsk.in"); 
#define MM 100000 
#define NN 100 
typedef struct Cseg { 
    int x,y,w; 
}Cseg; 
Cseg l[MM]; 
int n,m,flag[NN]; 
void in(); 
int mycmp(const void *pp,const void *qq); 
int clsk(); 
int min(int a,int b); 
int main() 
{ 
    int out; 
    in(); 
    out=clsk(); 
    if (out==-1) cout<<"No such tree."<<endl; 
    else cout<<out<<endl; 
    fin.close(); 
    return 0; 
} 
int clsk() 
{ 
    int i,j,count(0); 
    qsort(l,m,sizeof(Cseg),mycmp); 
    for (i=0;i<n;i++){ 
        flag=i; 
    } 
    j=0; 
    for (i=0;i<m;i++) 
    { 
        int nx,ny; 
        nx=l.x; 
        ny=l.y; 
        if (flag[nx]!=flag[ny]){ 
            int _min,_x,_y,k; 
            _min=min(flag[nx],flag[ny]); 
            _x=flag[nx]; 
            _y=flag[ny]; 
            count+=l.w; 
            for (k=0;k<n;k++) 
                if (flag[k]==_x || flag[k]==_y) flag[k]=_min; 
            j++; 
        } 
    } 
    if (j!=n-1) return -1; 
    else return count; 
    
} 
void in() 
{ 
    int i; 
    fin>>n>>m; 
    for (i=0;i<m;i++) 
        fin>>l.x>>l.y>>l.w; 
    return; 
} 
int mycmp(const void *pp,const void *qq) 
{ 
    Cseg *p,*q; 
    p=(Cseg*)pp; 
    q=(Cseg*)qq; 
    if (p->w==q->w) return 0; 
    if (p->w>q->w) return 1; 
    return -1; 
} 
int min(int a,int b) 
{ 
    if (a<b) return a; 
    return b; 
}