C - Roads and Libraries HackerRank - torque-and-development 【 并查集 】

C - Roads and Libraries

HackerRank - torque-and-development 

题意：给一堆点与点之间有没有边，在某一些地方建图书馆，最后让每个城市都可以到达有图书馆的地方，每个点都可以建图书馆，也可以不建，在两个点之间建一条路，这样在任意一个点建一个图书馆就可以了。现在图书馆和路的花费给出来，为了让所有的点都可以到达图书馆，找一个最小答案。 题解：用并查集合并一下，就可以了。判断一下是建一条路贵还是建图书馆贵。

代码语言：javascript复制

#include <bits/stdc  .h>
using namespace std;
typedef long long ll;
const ll maxn =100005;
ll fa[maxn];
ll fin(ll x)
{
    return x == fa[x] ? x : fa[x] = fin(fa[x]);
}
void Un(ll x, ll y)
{
    ll a = fin(x);
    ll b = fin(y);
    if(a != b)
    {
        fa[a] = b;
    }
    return ;
}
int main()
{
    ll t,u,v;
    ll n,m,croad,clib;
    scanf("%lld", &t);
    while(t--)
    {
        scanf("%lld %lld %lld %lld", &n, &m, &clib, &croad);
        ll num = 0;
        num = n * clib;

        for(ll i = 1; i <= n; i   ) fa[i] = i;
        for(ll i = 0; i < m; i   )
        {
            scanf("%lld %lld", &u, &v);
            Un(u,v);
        }
        if(clib <= croad)
        {
            printf("%lldn",num);
        }
        else
        {
            ll sum = 0;
            for(ll i = 1; i <= n; i   )
            {
                if(fa[i] == i) sum  = clib;
                else sum  = croad;
            }
            printf("%lldn",sum);
        }
    }
    return 0;
}

libraries

0 人点赞