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

C - Roads and Libraries

 HackerRank - torque-and-development 

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

题解：用并查集合并一下，就可以了。判断一下是建一条路贵还是建图书馆贵。

#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("%lld\n",num);
        }
        else
        {
            ll sum = 0;
            for(ll i = 1; i <= n; i ++)
            {
                if(fa[i] == i) sum += clib;
                else sum += croad;
            }
            printf("%lld\n",sum);
        }
    }
    return 0;
}