简单的最小生成树，不过中间却弄了很久，究其原因，主要是第一次做生成树，很多细节不够熟练，find()函数的循环for判断条件是 pre[i]>=0,也就是遇到pre[i]==-1时停止，i就是并查集的代表元、
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#define MAXN 1000
#define MAXE 1000010
#define LEN 25
#define esp 1e-9 char name[MAXN][LEN];
int n,m; typedef struct
{
int u,v;
double w;
} EDGE; int dblcmp(double x)
{
if(fabs(x)<esp)
return ;
return x>?:-;
} int cmp(const void*i,const void*j)
{
EDGE *a=(EDGE*)i;
EDGE *b=(EDGE*)j;
return dblcmp(a->w-b->w);
} EDGE edge[MAXE];
int pre[MAXN]; int find(int x)
{
int i=x;
for(; pre[i]>=; i=pre[i]) ;
while(i!=x)
{
int t=pre[x];
pre[x]=i;
x=t;
}
return i;
} void link(int x,int y)
{
if(pre[x]>pre[y])
{
pre[x]+=pre[y];
pre[y]=x;
}
else
{
pre[y]+=pre[x];
pre[x]=y;
}
}
int p;/*记录edge数目的变量不要和输入数据的变量混用*/
void add_EDGE(int u,int v,double w)
{
edge[p].u=u;
edge[p].v=v;
edge[p].w=w;
p++;/*记得更新*/
} int match(char *s)
{
int i;
for(i=;i<n;i++)
if(strcmp(name[i],s)==)
break;
return i;
} double tot;
void input(void)
{
int i;
char s1[LEN],s2[LEN];
double w;
scanf("%lf%d",&tot,&n);
for(i=; i<n; i++)
scanf("%s",name[i]);
int u,v;
scanf("%d",&m);
for(i=; i<m; i++)
{
scanf("%s%s%lf",s1,s2,&w);
u=match(s1);
v=match(s2);
add_EDGE(u,v,w);
}
} double k(void)
{
int i,num=;
double ans=0.0;
qsort(edge,p,sizeof(EDGE),cmp);
/* for(i=0;i<p;i++)
printf("%d %d %f\n",edge[i].u,edge[i].v,edge[i].w); */
for(i=;i<p;i++)
{
int u=edge[i].u;
int v=edge[i].v;
int x,y;
if((x=find(u))!=(y=find(v)))
{
ans+=edge[i].w;
num++;
link(x,y);
}
if(num==n-)
break;
}
return ans;
} void solve(void)
{
memset(pre,-,sizeof(pre));
double mst=k();
/*printf("%lf\n",mst);*/
if(mst>tot)
puts("Not enough cable");
else printf("Need %.1f miles of cable\n",mst);
} int main(void)
{
input();
solve();
return ;
}