克鲁斯卡 (Clsk) 求最小生成树
源代码在线查看: 克鲁斯卡 (clsk) 求最小生成树.txt
#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;
}