Friday, August 9, 2019

Lightoj-1059 .cpp file

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef pair< int, int > pii;
typedef pair< int, pii > edge;
const int MAXN = 10001, MAXE = 100001;
int parent[MAXN];
edge G[MAXE], MST[MAXE];
bool flag[MAXN];
int find(int u)
{
    if(u==parent[u]) return parent[u];
      else  parent[u] = find(parent[u]);

}

int main()
{
    int t, cs = 1, i;
    int N, E, mstE, u, v, w, cnt;
    long long total, acost;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%lld", &N, &E, &acost);
        for(i = 1; i <= N; i++)
        {
            parent[i] = i;
            flag[i] = 0;
        }
        for(i = 0; i < E; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            G[i] = edge(w, pii(u, v));
        }
        sort(G, G+E);
        total = mstE = cnt = 0;
        for(i = 0; i < E; i++)
        {
            u = find(G[i].second.first);
            v = find(G[i].second.second);
            w = G[i].first;
            if(u != v)
            {
                MST[mstE++] = G[i];
                total += (long long)w;
                parent[u] = parent[v];
            }
        }
        for(i = 1; i <= N; i++)
        {
            u = find(i);
            if(!flag[u])
            {
                flag[u] = 1;
                cnt++;
            }
        }
        total += acost * cnt;
        for(i = mstE-1; i>=0; i--)
        {
            if(MST[i].first >= acost)
            {
                cnt++;
                total -= MST[i].first;
                total += acost;
            }
            else break;
        }
        printf("Case %d: %lld %d\n", cs++, total, cnt);
    }
    return 0;
}

No comments:

Post a Comment