题解 | #最小生成树#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这n户人家连接起来
 * @param n int整型 n户人家的村庄
 * @param m int整型 m条路
 * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
 * @param costRowLen int cost数组行数
 * @param costColLen int* cost数组列数
 * @return int整型
 */
#define MAX 10000000
int find(int*parent,int i)
{
    while(parent[i]!=MAX)
    {
        i=parent[i];
    }
    return i;
} 
void merge(int**cost,int**cost1,int i,int m,int n)
{
    int k=i;
    int j,l;
    for(j=m+1;i<=m&&j<=n;k++)
    {
        if(cost[i][2]<cost[j][2])
        {
            cost1[k]=cost[i];
            i++;
        }
        else
        {
            cost1[k]=cost[j];
            j++;        
        }
    }
    if(i<=m)
    {
        for(l=0;l<=m-i;l++)
        {
           cost1[k+l]=cost[i+l];
        }
    }
    if(j<=n) 
    {
        for(l=0;l<=n-j;l++)
        {
          cost1[k+l]=cost[j+l];
        }
    }

}
void mergesort(int**cost,int**cost1,int s,int t,int k)
{
    int i=s;
    int j;
    while(i<=t-2*k+1)
    {
        merge(cost,cost1,i,k+i-1,i+2*k-1);
        i=i+2*k;
    }
    if(i<t-k+1)
    {
        merge(cost,cost1,i,i+k-1,t);
    }
    else 
    {
        for(j=i;j<=t;j++)
        {
          cost1[j]=cost[j];
        }
    }

}
int miniSpanningTree(int n, int m, int** cost, int costRowLen, int* costColLen ) {
    int i,j,a,b;
    int parent[n+1];
    int min;
    int *p;
    int lowcost=0;
    int arr[3]={1,1,1};
    int**cost1=(int**)malloc(m*sizeof(int*));
    for(i=0;i<m;i++)
    {
        cost1[i]=arr;
    }
    // printf("%d",2);
    // printf("%d",20);
    int k=1;
    while(k<m)
    {
        mergesort(cost,cost1,0,m-1,k);
        k=k*2;
        mergesort(cost1,cost,0,m-1,k);
        k=k*2;
    }
    // for(i=0;i<m;i++)
    // {
    //     for(j=0;j<m;j++)
    //     {
    //         printf("%d",cost[i][j]);
    //     }
    // }
    for(i=0;i<n+1;i++)
    {
        parent[i]=MAX;
    }
    for(i=0;i<m;i++)
    {
        a=find(parent,cost[i][0]);
        b=find(parent,cost[i][1]);
        if(a!=b)
        {
            parent[a]=b;
            lowcost+=cost[i][2];
        }
        
    }
    return lowcost;


    // write code here
}