#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct node
{
    int x,y;double d;
}a[2110000];int n,m,len,fa[1100];
int findfa(int x)
{
    if(fa[x]==x)return x;
	else
	{
		fa[x]=findfa(fa[x]);
		return fa[x];
	}
}
int cmp(const void *x1,const void *x2)
{
    node n1=*(node *)x1;
	node n2=*(node *)x2;
	if(n1.d>n2.d)return 1;
	else return -1;
}
char s[11000][30];
char ss[30];
int main()
{
	double tf;len=0;
	scanf("%lf",&tf);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)scanf("%s",s[i]+1);
	scanf("%d",&len);
	for(int i=1;i<=len;i++)
	{
		int x=0,y=0;double k;
		scanf("%s",ss+1);
		for(int j=1;j<=m;j++)
		{
		    if(strcmp(s[j]+1,ss+1)==0)x=j;
		}
		scanf("%s",ss+1);len=strlen(ss+1);
		for(int j=1;j<=m;j++)
		{
		    if(strcmp(s[j]+1,ss+1)==0)y=j;
		}
		scanf("%lf",&k);
		a[i].x=x;a[i].y=y;a[i].d=k;
	}
	qsort(a+1,len,sizeof(node ),cmp);
	for(int i=1;i<=m;i++)fa[i]=i;
	double ans=0.00000000;int t=0;
	for(int i=1;i<=len;i++)
	{
		int fx,fy;
		fx=findfa(a[i].x);
		fy=findfa(a[i].y);	
		if(fx!=fy)
		{
		    ans+=a[i].d/1.0;
			fa[fy]=fx;
			t++;
			if(t==len-1)break;
		}
	}
	if(ans<=tf)printf("Need %.1f miles of cable\n",ans);
	else printf("Not enough cable\n");
}

• Re:错误代码大公布............. (1409) huangzhengdoc 2015-08-22 08:51:32