次小生成树.txt

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

/*
具体方法系先用prim求最小生成树，同时保存任意两点间在树中通路权最大的边，
在剩下的边中枚举找出“连接该边两点间权重最大边”的权值和“该边权值”之差，
将其差为正且最小的，替换。
我觉得呢个算法重复调用k次可求k小生成树，效率o(kv^2)，比较大请问有无更好既方法？
*/
#include <stdio.h>
#include <queue>
#include <algorithm>
#define N 101
#define M 1<<30
using namespace std;

struct points
{
 int road[N];
 int len[N];
 int num;
}point[N]={0};

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

int n;
que u[N][N]={0};
bool fin[N][N]={0};

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

void make(int a,que use)
{
 int b=use.end,c=use.beg,d=a;
 if(a==b) return ; 
 if(a>b) swap(a,b);
 if(d>c) swap(c,d);

 if(u[d][c].len<use.len) u[a][b]=use;
 else u[a][b]=u[d][c];
 if(u[a][b].beg>u[a][b].end) swap(u[a][b].beg,u[a][b].end);
}

int findtree(que use)
{
 int a,b;
 a=use.beg;b=use.end;
 if(a>b) swap(a,b);
 if(fin[a][b]) return M;
 fin[a][b]=true;
 return use.len-u[a][b].len;
}

void heapin(int a)
{
 int i;
 que mid;
 for(i=0;i<point[a].num;i++)
 {
  mid.len=point[a].len[i];
  mid.end=point[a].road[i];
  mid.beg=a;
  mini.push(mid);
 }
}

void prim(int first)
{
 int i,j,num=0,res=0,Min=M,pla;
 bool check[N]={0};
 que q[N]={0};
 que mid;

 heapin(first);
 check[first]=true;

 while(!mini.empty())
 {
  mid=mini.top();
  mini.pop();

  if(check[mid.beg]&&check[mid.end])
  {q[num++]=mid;continue;}

  check[mid.end]=true;
  fin[mid.end][mid.beg]=fin[mid.beg][mid.end]=true;
  for(j=1;j<=n;j++) if(check[j]) make(j,mid);

  res+=mid.len;
  j=mid.end;
  heapin(j);
 }

 for(i=0;i<num;i++)
 {
  j=findtree(q[i]);
  if(j<Min&&j) {Min=j;pla=i;}
 }
 res+=Min;

 printf("\n%d\n",res);
}

int main()
{
 int i,m,a,b,c;
 scanf("%d %d",&n,&m);
 while(m--)
 {
  scanf("%d %d %d",&a,&b,&c);
  point[a].road[point[a].num]=b;
  point[a].len[point[a].num]=c;
  point[a].num++;
  point[b].road[point[b].num]=a;
  point[b].len[point[b].num]=c;
  point[b].num++;
 }
 prim(1);
 scanf("%d",&i);
}