- Kerry 的电缆网络
- 2016-05-22 19:54:19 @
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
using namespace std;
struct edge
{
int x,y;double s1;
}e[100000];
double s;
int n,m=1,i,j;
int f[100000];
bool cmp(edge a,edge b)
{
return a.s1<b.s1;
}
int find(int i)
{
if (f[i]==i) return i;
return f[i]=find(i);
}
void uni(int i,int j)
{
f[j]=find(i);
}
int main()
{
// freopen("vijos1045.in","r",stdin);
scanf("%lf",&s);
scanf("%d",&n);
memset(e,0,sizeof(e));
while(scanf("%d%d%lf\n",&e[m].x,&e[m].y,&e[m].s1)!=-1)m++;
sort(e+1,e+m+1,cmp);
for (i=1;i<=n;i++)f[i]=i;
int rst=n;double ans=0;
for (i=1;i<=m && rst>1;i++)
{
if (find(e[i].x)!=find(e[i].y))
{
uni(e[i].x,e[i].y);
rst--;
ans+=e[i].s1;
}
}
if(ans>s)printf("impossible/n");
else printf("Need %.2f miles of cable",ans);
return 0;
}
0 条评论
目前还没有评论...