克鲁斯卡 (Clsk) 求最小生成树

源代码在线查看: 克鲁斯卡 (clsk) 求最小生成树.txt

软件大小: 2 K
上传用户: liangshuo800
关键词: Clsk 生成树
下载地址: 免注册下载 普通下载 VIP

相关代码

				#include       // 克鲁斯卡 (Clsk) 求最小生成树。l[n]为无向图各个 
				边的信息。 
				#include      // n为顶点数,m为边数,函数clsk()返回最小代价值。 
				#include        // 坐标一律以 0 开始。 
				#include  
				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				    else cout				    fin.close(); 
				    return 0; 
				} 
				int clsk() 
				{ 
				    int i,j,count(0); 
				    qsort(l,m,sizeof(Cseg),mycmp); 
				    for (i=0;i				        flag=i; 
				    } 
				    j=0; 
				    for (i=0;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				                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				        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				    return b; 
				} 
							

相关资源