kruskal.txt

图论常用算法的C语言程序,对于图论的一些应用有很大的指导作用!

#include <stdio.h>          //并查集可能有问题，顺便帮手睇睇 ^_^
#include <queue>
#include <algorithm>
#define N 1010
#define M 1<<30
using namespace std;

struct que
{
 int len;
 int beg;
 int end;
};

bool operator <(const que &x,const que &y)
{
 if(x.len>y.len) return true;
 return false;
}
priority_queue<que> mini;

int m[N]={0};

void init(int n)
{
 int i;
 for(i=0;i<=n;i++) m[i]=0;
}

int sea(int a)
{
 int mid=M;
 while(1)
 {
  if(!m[a]) return a;
  m[mid]=m[a];
  mid=a;
  a=m[a];
 }
}

void uni(int a,int b)
{
 if(a==b) return ;
 m[a]=b;
}

int kruskal()
{
 int a,b,fa,fb,res=0;
 que mid;
 while(!mini.empty())
 {
  mid=mini.top();
  mini.pop();
  a=mid.beg;b=mid.end;
  fa=sea(a);fb=sea(b);
  if(fa==fb) continue;
  uni(fa,fb);
  res+=mid.len;
 }
 return res;
}

int main()
{
 int n,m,i,a,b,c;
 que mid;
 scanf("%d %d",&n,&m);
 init(m);
 for(i=1;i<=n;i++)
 {
  scanf("%d %d %d",&a,&b,&c);
  mid.beg=a;mid.end=b;mid.len=c;mini.push(mid);
 }
 printf("%d\n",kruskal());
 scanf("%d",&i);
}