11

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

 4 years ago
source link: https://arminli.com/vijos-p1045/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Armin's Blog

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;
}
Profile picture

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK