VIJOS-P1045 Kerry的电缆网络（并查集）

February 24, 2016

题目链接

按照长度排序，然后并查集即可。

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int fa[100005];
int n;
double ans, S;

struct edge{
    int x, y;
    double l;
}E[100005];

int findfa(int x){
    if(fa[x] != x){
        fa[x] = findfa(fa[x]);
    }
    return fa[x];
}

void add(int x, int y, double k){
    if(x > y)
        swap(x, y);
    x = findfa(x);
    y = findfa(y);
    if(x != y){
        fa[y] = x;
        ans += k;
    }
}

bool cmp(edge a, edge b){
    return a.l < b.l;
}

int main(){
    //freopen("a.txt", "r", stdin);
    int m = 1;
    scanf("%lf %d", &S, &n);
    while(scanf("%d %d %lf", &E[m].x, &E[m].y, &E[m].l) != EOF){
        m++;
    }m--;
    for(int i = 1; i <= n; i++)
        fa[i] = i;
    sort(E+1, E+m+1, cmp);
    ans = 0;
    for(int i = 1; i <= m; i++){
        add(E[i].x, E[i].y, E[i].l);
    }
    bool flag = 0;
    int x = findfa(1);
    for(int i = 2; i <= n; i++){
        if(findfa(i) != x){
            flag = 1;
            break;
        }
    }
    if(ans-S > 1e-6 || flag)
        cout << "Impossible" << endl;
    else
        printf("Need %.2f miles of cablen", ans);
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]