记:
本题目考的是最小生成数，可使用Kruskal算法
第一次，20分 原因:使用动态数组，有概率报运行错误(大雾= =)
第二次，100分 原因:改用静态数组，一次过
示例代码:
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999 typedef struct node node_t;
typedef struct node
{
int S;
int E;
int L;
}node;
node e[]; int N,P; /*N个结点，P条路*/
int c[]; /*纪录在牧场逗留的时间*/
int d[]; /*纪录牧场之间的距离*/ void sort(int x, int y)
{
int i = x , j = y;
node p;
p = e[i];
if (i < j)
{
while (i < j)
{
while (i < j && e[j].L > p.L)
{
j --;
}
if (i < j)
{
e[i] = e[j];
i ++;
}
while (i < j && e[i].L < p.L)
{
i ++;
}
if (i < j)
{
e[j] = e[i];
j --;
}
}
e[i] = p;
sort(x,i-);
sort(i+,y);
}
return ;
} int find(int x)
{
if (x == d[x])
{
return x;
}
d[x] = find(d[x]);
return d[x];
} int Kruskal()
{
int i;
int S,E;
int sum = , count = ;
for (i = ; i <= N ; i ++)
{
d[i] = i;
} sort(,P); for (i = ; i <= P ; i++)
{
S = find(e[i].S);
E = find(e[i].E);
if (S != E)/*两点没有交集*/
{
sum += e[i].L;
d[S] = e[i].E;
count ++;
if (count == N)
{
break;
}
}
}
return sum;
} int main(void)
{
int i = , min = INF;
int S,E,L; scanf("%d %d",&N,&P); for (i = ; i <= N ; i ++)
{
scanf("%d",&c[i]);
if (c[i] < min)
{
min = c[i];
}
} for (i = ; i <= P ; i ++)
{
scanf("%d %d %d",&S,&E,&L);
e[i].S = S;
e[i].E = E;
e[i].L = L* + c[S] + c[E];
} printf("%d",min+Kruskal());
return ;
}