HackerEarth Lottery problem solution

In this HackerEarth Lottery problem solution There is a lottery winner who has lives in a house which has R * C rooms such that there are R rows where each row has C rooms and C columns and each column has R rooms, he will receive N coins worth Xi $ as a winner. He will place each coin in one of R * C rooms and also note that more than one coin can be placed in a single room. You will be given which rooms he has chosen. Now robbers have known about the coins and want to loot him as much as possible. Robbers will do the following:

1. Column wise: For every column they will choose at most one coin to rob.
2. Row wise: For every row they will choose one coin to rob.

If they rob coin i, they will get an amount worth Xi and it is obivious that robbed coins will not be persent. They will rob optimally.

What is the maximum possible sum of amount robbers can rob?

HackerEarth Lottery problem solution.

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define endl "\n"
#define test ll t; cin>>t; while(t--)
typedef long long int ll;
struct edge{
    ll u,v,w;
};
bool cmp(edge e1,edge e2){
    return e1.w>e2.w;
}
class dsu{
    public:
    vector<ll>par,f,sz;
    dsu(ll n){
        par.resize(n); f.resize(n); sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=-1; f[i]=0; sz[i]=1;
        }
    }
    ll get(ll x){
        return (par[x]==-1?x:(par[x]=get(par[x])));
    }
    bool unite(ll x,ll y){
        x=get(x);
        y=get(y);
        if(x==y){
            if(f[x]) return false;
            f[x]=true;
            return true;
        }
        if(f[x] && f[y]) return false;
        if(sz[x]>sz[y]) swap(x,y);
        sz[y]+=sz[x];
        if(f[y]==0 && f[x]==1) f[y]=1;
        par[x]=y;
        return true;
    }
};
int main() {
    FIO;
    test
    {
       ll k,n,m; cin>>k>>n>>m;
       vector<edge>ad(k);
       for(int i=0;i<k;i++){
           cin>>ad[i].u>>ad[i].v>>ad[i].w;
           ad[i].u--;
           ad[i].v+=(n-1);
       }
       sort(ad.begin(),ad.end(),cmp);
       ll nodes=n+m;
       dsu d(nodes);
       ll ans=0;
       for(auto it:ad){
           if(d.unite(it.u,it.v)){
               ans+=it.w;
           }
       }
       cout<<ans<<endl;
    }
    return 0;
}

Second solution

t = int(input())
while t > 0:
    t -= 1
    n, r, c = map(int, input().split())
    edges = []
    for i in range(n):
        x, y, z = map(int, input().split())
        x -= 1
        y += r - 1
        edges += [[x, y, z]]
    edges.sort(key=lambda v: v[2], reverse=True)
    par = [i for i in range(r + c)]
    full = [False] * (r + c)


    def root(x):
        chain = [x]
        while par[chain[-1]] != chain[-1]:
            chain += [par[chain[-1]]]
        for v in chain:
            par[v] = chain[-1]
        return par[x]


    def merge(v, u) -> bool:
        v = root(v)
        u = root(u)
        if full[v] and full[u]:
            return False
        if v == u:
            full[v] = True
            return True
        full[v] |= full[u]
        par[u] = v
        return True


    ans = 0
    for x, y, z in edges:
        if merge(x, y):
            ans += z
    print(ans)