RTE 的原因?

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
int n,m,i,tot,r[1000010],father[1000010];
double answer,ans,len;
using namespace std;
struct kruskal{
    int u;
    int v;
    double w;
};
kruskal e[100010];
bool cmp_(int a,int b){
    return e[a].w<e[b].w;
}
int find(int x){
    return father[x]==x?x:father[x]=find(father[x]);
}
double kruskal(){
    for (int i=1;i<=n;i++)
        father[i]=i;
    for (int i=1;i<=m;i++)
        r[i]=i;
    sort(r+1,r+m+1,cmp_);
    int k=0;double ans=0;
    for (int i=1;i<=m;i++){
        int x;int y;
        x=find(e[r[i]].u);y=find(e[r[i]].v);
        if (x!=y) {
            ans+=e[r[i]].w;
            father[x]=y;
            tot++;
        }
        if (tot==n-1){
            break;
        }
    }    
    int root=find(1);
    for (int i=1;i<=n;i++)
        if (find(i)!=root) return -1;
    return ans;
}
int main(){
    scanf("%lf",&len);
    scanf("%d",&n);
    while (~scanf("%d%d%lf",&e[i].u,&e[i].v,&e[i].w)==3)
        m++;
    m--;
    answer=kruskal();
    if (answer<=len) printf("Need %.2lf miles of cable",answer);
    else printf("Impossible");
} 

0 条评论

目前还没有评论...

信息

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