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
分类
树结构 点击显示
标签
(无)
递交数
4932
已通过
1000
通过率
20%
被复制
10
上传者