Problem:
 Score : 800 points    Problem Statement There are N cards placed on a grid with H rows and W columns of squares.  The i -th card has an integer A_i written on it, and it is placed on the square at the R_i -th row from the top and the C_i -th column from the left.  Multiple cards may be placed on the same square.  You will first pick up at most one card from each row.  Then, you will pick up at most one card from each column.  Find the maximum possible sum of the integers written on the picked cards.      Constraints  All values are integers.  1 \leq N \leq 10^5  1 \leq H, W \leq 10^5  1 \leq A_i \leq 10^5  1 \leq R_i \leq H  1 \leq C_i \leq W         Input Input is given from Standard Input in the following format:  N  H  W  R_1  C_1  A_1  R_2  C_2  A_2  \vdots  R_N  C_N  A_N       Output Print the maximum possible sum of the integers written on the picked cards.        Sample Input 1 6 2 2
2 2 2
1 1 8
1 1 5
1 2 9
1 2 7
2 1 4      Sample Output 1 28  The sum of the integers written on the picked cards will be 28 , the maximum value possible, if you pick up cards as follows:   Pick up the fourth card from the first row.  Pick up the sixth card from the second row.  Pick up the second card from the first column.  Pick up the fifth card from the second column.        Sample Input 2 13 5 6
1 3 35902
4 6 19698
4 6 73389
3 6 3031
3 1 4771
1 4 4784
2 1 36357
2 1 24830
5 6 50219
4 6 22645
1 2 30739
1 4 68417
1 5 78537      Sample Output 2 430590       Sample Input 3 1 100000 100000
1 1 1      Sample Output 3 1

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5)


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
        self.taken = [0] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            new_root = r1
        else:
            d1 = self.table[r1]
            d2 = self.table[r2]
            if d1 <= d2:
                self.table[r2] = r1
                self.table[r1] += d2
                self.taken[r1] += self.taken[r2]
                new_root = r1
            else:
                self.table[r1] = r2
                self.table[r2] += d1
                self.taken[r2] += self.taken[r1]
                new_root = r2

        cells = -self.table[new_root]
        taken = self.taken[new_root]
        if cells > taken:
            self.taken[new_root] += 1
            return True
        return False


n, h, w = map(int, input().split())
hw = h + w
cards = []
for line in sys.stdin:
    r, c, a = map(int, line.split())
    cards.append((a, r - 1, h + c - 1))
cards.sort(reverse=True)

uft = UnionFind(hw)
ans = 0

for a, r, c in cards:
    if uft.union(r, c):
        ans += a
print(ans)

Solution (Python):
import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def get_group(k):
        g = pd[k]
        if g < 0:
            return k
        gg = get_group(g)
        pd[k] = gg
        return gg

    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            d1 = -pd[g1]
            d2 = -pd[g2]
            if d2 > d1:
                g1, g2 = g2, g1
            pd[g2] = g1
            if d1 == d2:
                pd[g1] -= 1

    hp = []
    n, h, w = map(int, input().split())
    pd = [-1] * (h + w + 2)  
    pd[0] = -(h + w + 2)
    for _ in range(n):
        r, c, a = map(int, input().split())
        heappush(hp, [-a, r, h + c])
    cnt = h + w
    ans = 0
    while cnt and hp:
        a, r, c = heappop(hp)
        gr = get_group(r)
        gc = get_group(c)
        if gr + gc == 0: continue
        if gr == gc:
            merge(gr, 0)
        else:
            merge(gr, gc)
        ans -= a
        cnt -= 1
    print(ans)

main()

Solution (Python):
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*n
		self.rank = [0]*n
		self.cycle = [False]*n

	def find(self, x):
		if(self.root[x] < 0):
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if(x == y):
			self.cycle[x] = True
		elif(self.rank[x] > self.rank[y]):
			self.root[x] += self.root[y]
			self.cycle[x] |= self.cycle[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.cycle[y] |= self.cycle[x]
			self.root[x] = y
			if(self.rank[x] == self.rank[y]):
				self.rank[y] += 1

	def isSame(self, x, y):
		return self.find(x) == self.find(y)
	
	
	def isSafe(self, x, y):
		cx = self.cycle[self.find(x)] 
		cy = self.cycle[self.find(y)]
		return not((self.isSame(x,y) and (cx or cy)) or (cx and cy))

n,h,w,*l = map(int,open(0).read().split())
cards = sorted([(a,r-1,c-1) for r,c,a in zip(*[iter(l)]*3)])[::-1]
uf = UnionFind(h+w)
ans = 0

for a,r,c in cards:
	c += h
	if uf.isSafe(r,c):
		uf.unite(r,c)
		ans += a
print(ans)

Solution (Python):
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*n
		self.rank = [0]*n
		self.cycle = [False]*n

	def find(self, x):
		if(self.root[x] < 0):
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if(x == y):
			self.cycle[x] = True
		elif(self.rank[x] > self.rank[y]):
			self.root[x] += self.root[y]
			self.cycle[x] |= self.cycle[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.cycle[y] |= self.cycle[x]
			self.root[x] = y
			if(self.rank[x] == self.rank[y]):
				self.rank[y] += 1

	def isSame(self, x, y):
		return self.find(x) == self.find(y)
	
	
	def isSafe(self, x, y):
		cx = self.cycle[self.find(x)] 
		cy = self.cycle[self.find(y)]
		return not((self.isSame(x,y) and (cx or cy)) or (cx and cy))

n,h,w,*l = map(int,open(0).read().split())
cards = sorted([(a,r-1,c-1) for r,c,a in zip(*[iter(l)]*3)])[::-1]
uf = UnionFind(h+w)
ans = 0

for a,r,c in cards:
	c += h
	if uf.isSafe(r,c):
		uf.unite(r,c)
		ans += a
print(ans)

Solution (Python):
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rank = [0]*(n+1)
		self.cycle = [False]*(n+1)

	def find(self, x):
		if(self.root[x] < 0):
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if(x == y):
			self.cycle[x] = True
		elif(self.rank[x] > self.rank[y]):
			self.root[x] += self.root[y]
			self.cycle[x] |= self.cycle[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.cycle[y] |= self.cycle[x]
			self.root[x] = y
			if(self.rank[x] == self.rank[y]):
				self.rank[y] += 1

	def isSame(self, x, y):
		return self.find(x) == self.find(y)
		
	def isCycle(self, x, y):
		cx = self.cycle[self.find(x)]
		cy = self.cycle[self.find(y)]
		if cx == cy == False:
			return False
		elif cx ^ cy:
			return True
		else:
			return 2

	def size(self, x):
		return -self.root[self.find(x)]

n,h,w,*l = map(int,open(0).read().split())
cards = sorted([(a,r,c) for r,c,a in zip(*[iter(l)]*3)])[::-1]

uf = UnionFind(h+w)
ans = 0

for a,r,c in cards:
	c += h
	if not ( (uf.isSame(r,c) and uf.isCycle(r,c)) or uf.isCycle(r,c)==2 ):
		uf.unite(r,c)
		ans += a
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def par(a):
    if P[a] < 0: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) == par(b): return 0
    C[par(a)], C[par(b)] = C[par(a)] + C[par(b)], C[par(a)] + C[par(b)]
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)
N, H, W = map(int, input().split())
P = [-1 for i in range(H+W)]
C = [1] * (H+W)
X = []
for _ in range(N):
    r, c, a = map(int, input().split())
    X.append((a, r-1, c+H-1))
X = sorted(X)
ans = 0
while X:
    a, r, c = X.pop()
    unite(r, c)
    if C[par(r)]:
        ans += a
        C[par(r)] -= 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def par(a):
    if P[a] < 0: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) == par(b): return 0
    C[par(a)], C[par(b)] = C[par(a)] + C[par(b)], C[par(a)] + C[par(b)]
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)
N, H, W = map(int, input().split())
P = [-1 for i in range(H+W)]
C = [1] * (H+W)
X = []
for _ in range(N):
    r, c, a = map(int, input().split())
    X.append((a, r-1, c+H-1))
X = sorted(X)
ans = 0
while X:
    a, r, c = X.pop()
    unite(r, c)
    if C[par(r)]:
        ans += a
        C[par(r)] -= 1
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    m,d = LI()
    ans = 0
    for i in range(1,m+1):
        for j in range(1,d+1):
            d1 = j%10
            d2 = j//10
            if d1 >= 2 and d2 >= 2 and d1*d2 == i:
                ans += 1
    print(ans)
    return


def B():
    def add(i):
        while i <= m:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n,k = LI()
    m = 2000
    a = LI()
    bit = [0]*(m+1)
    ans = 0
    for i in range(n):
        ans += (i-sum(a[i]))*k
        add(a[i])
    inv = pow(2,mod-2,mod)
    for i in range(n):
        ans += sum(a[i]-1)*k*(k-1)*inv%mod
    print(ans%mod)
    return


def C():
    n = I()
    s = S()
    if "W" in (s[0],s[-1]):
        print(0)
        return
    d = [0]
    for i in range(1,2*n):
        if s[i] == s[i-1]:
            d.append(1-d[-1])
        else:
            d.append(d[-1])
    if sum(d) != n:
        print(0)
        return
    ans = 1
    s = 0
    for i in d:
        if not i:
            s += 1
        else:
            ans *= s
            s -= 1
            ans %= mod
    for i in range(1,n+1):
        ans *= i
        ans %= mod
    print(ans)
    return


def D():
    n = I()
    m = n.bit_length()
    v = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            k = i^j
            for l in range(m):
                if k&(1<<l):
                    v[i][j] = l+1
                    break
    for i in range(n-1):
        print(*v[i][i+1:])
    return


def E():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            s[y] += s[x]
            e[y] += e[x]+1
        else:
            par[y] = x
            s[x] += s[y]
            e[x] += e[y]+1
            if rank[x] == rank[y]:
                rank[x] += 1

    n,h,w = LI()
    v = []
    m = h+w
    for i in range(n):
        r,c,a = LI()
        r -= 1
        c += h-1
        v.append((a,r,c))
    v.sort(key = lambda x:-x[0])
    par = [i for i in range(m)]
    rank = [0]*m
    s = [1]*m
    e = [0]*m
    ans = 0
    for a,x,y in v:
        rx,ry = root(x), root(y)
        if rx == ry:
            if e[rx]+1 <= s[rx]:
                ans += a
                e[rx] += 1
        else:
            if e[rx]+e[ry]+1 <= s[rx]+s[ry]:
                ans += a
                unite(x,y)
    print(ans)
    return


def F():

    return


if __name__ == "__main__":
    E()

Solution (Python):
import sys
input=sys.stdin.readline
class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.rank=[0]*n
        self.size=[1]*n
        self.Ecnt=[0]*n
    def root(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.root(self.par[x])
            return self.par[x]
    def union(self,x,y):
        px=self.root(x); py=self.root(y)
        if px!=py:
            if self.rank[px]==self.rank[py]:
                self.rank[px]+=1
            elif self.rank[px]<self.rank[py]:
                px,py=py,px
            self.par[py]=px
            self.size[px]+=self.size[py]
            self.Ecnt[px]+=self.Ecnt[py]+1
        else:
            self.Ecnt[px]+=1
    def same_check(self,x,y):
        return self.root(x)==self.root(y)

n,h,w=map(int,input().split())
RCA=[]
for _ in range(n):
    r,c,a=map(int,input().split())
    r-=1
    c+=h-1
    RCA.append((r,c,a))
RCA.sort(lambda x:x[2],reverse=True)
uf=UnionFind(h+w)
ans=0
for r,c,a in RCA:
    if uf.same_check(r,c):
        if uf.size[uf.par[r]]>uf.Ecnt[uf.par[r]]:
            uf.union(r,c)
            ans+=a
    else:
        if (uf.size[uf.par[r]]+uf.size[uf.par[c]])>(uf.Ecnt[uf.par[r]]+uf.Ecnt[uf.par[c]]):
            uf.union(r,c)
            ans+=a
print(ans)

Solution (Python):


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) 
        self.size = [1]*n 
        self.cycle = [0]*n
 
    def root(self, x): 
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x 
        self.size[x] += self.size[y] 
        self.parent[y] = x 
        self.cycle[x] = self.cycle[x]+self.cycle[y]
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def getsize(self,x): 
        return self.size[self.root(x)]

    def getcycle(self,x): 
        return self.cycle[self.root(x)]

    def addcycle(self,x): 
        self.cycle[self.root(x)]+=1
        return 

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 
 

n,h,w = [int(i) for i in readline().split()]


uf = UnionFind(h+w)

rca = [[int(i)-1 for i in readline().split()] for i in range(n)]

from operator import itemgetter
rca.sort(key = itemgetter(2), reverse=True)

ans = 0

for r,c,a in rca:
    c += h
    a += 1
    if uf.issame(r,c):
        if uf.getcycle(r): continue
        ans += a
        uf.addcycle(r)
    else:
        if uf.getcycle(r)+uf.getcycle(c) >= 2: continue
        uf.merge(r,c)
        ans += a

print(ans)