#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 条评论

目前还没有评论...

信息

ID
1045
难度
7
分类
树结构 点击显示
标签
(无)
递交数
4912
已通过
986
通过率
20%
被复制
5
上传者