分析:就是求最小生成树中 权值最长的边 ,用 prim
#include<stdio.h>
#include<memory.h>
#define MAX 1000000
int n,G[510][510],lowcost[510],vis[510];
int prim()
{int i,j,pos=1,min,result=0,ans=0;memset(vis,0,sizeof(vis));vis[pos]=1;for(i=1;i<=n;i++)if(i!=pos)lowcost[i]=G[pos][i];for(i=1;i<n;i++){
min=MAX;for(j=1;j<=n;j++)
if(vis[j]==0 && min>lowcost[j]){min=lowcost[j];pos=j;}
result+=min;if(min>ans)ans=min;vis[pos]=1;for(j=1;j&l......
阅读全文