最小生成树-白红宇

最小生成树

阅读量：4205 次

发布时间：2019-05-26

本文共 1653 字，大约阅读时间需要 5 分钟。

最小生成树带判断连通 HDU1863

也是函数直接用就行

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define MIN INT_MAX#define MAX_Point 120 //最大的顶点数#define MAX_Edge 14400   //最大的边数int flag1=0;double sum ;double arr_list[MAX_Point][MAX_Point] ;struct Edge{   int point ;   double lowcost ;   int flag;} ;Edge edge[MAX_Edge] ;double prim( int n )// n表示树顶点的个数！{    int i , j , k = 1,flag ;   double min,sum2=0 ;   j = 1 ;   for( i = 1 ; i< = n ; i ++ )   {       if (i != j )       {           edge[i].point = i ;           edge[i].lowcost = arr_list[j][i] ;           edge[i].flag=0;       }   }   edge[j].lowcost = 0 ; edge[j].flag=1;   for( i = 2 ; i< = n ; i++ )   {       k=1;       min = MIN ;       flag=0;       for( j=2;j<=n; j++ )       {           if ( edge[j].flag== 0 && edge[j].lowcost < min)           {               k = j ;               min = edge[j].lowcost ;               flag=1;           }       }       if (!flag) return -1;                  sum2 += min ;            edge[k].flag=1;       for(j = 2 ; j <= n ; j++ )       {           if( edge[j].flag== 0&&arr_list[k][j] < edge[j].lowcost)           {               edge[j].point = k ;               edge[j].lowcost = arr_list[k][j] ;           }       }   } return sum2;}int main(int argc, char *argv[]){    double t,time_data;    int n,m;    int a,b;    while(cin>>n>>m)    {     if (n==0) break;     sum=0;     for(int i=1;i<=m;i++)        for(int j=1;j<=m;j++)          arr_list[i][j]=INT_MAX;          for(int i=1;i<=n;i++)         {             cin>>a>>b>>time_data;       //下面很关键 边界数据 没有就AC 不了    if (time_data