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



Sample input:
6 2 2
2 2 2
1 1 8
1 1 5
1 2 9
1 2 7
2 1 4


Sample output:
28

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import operator

N,H,W = map(int,readline().split())
RCA = [int(x) for x in read().split()]
it = iter(RCA)
RCA = sorted(zip(it,it,it),key=operator.itemgetter(2),reverse=True)

root = list(range(H+W))
size = [0] * (H+W)
no_cycle = [True] * (H+W)

def find_root(x):
    y = root[x]
    if x == y:
        return y
    z = find_root(y)
    root[x] = z
    return z

def merge(x,y):
    x,y = find_root(x),find_root(y)
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    no_cycle[x] = (no_cycle[x] and no_cycle[y])

answer = 0
for R,C,A in RCA:
    x,y = R-1,H+C-1
    rx,ry = find_root(x),find_root(y)
    if rx == ry:
        if not no_cycle[rx]:
            continue
        no_cycle[rx] = False
    else:
        if (not no_cycle[rx]) and (not no_cycle[ry]):
            continue
        #merge(rx,ry)
    answer += A

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import operator

N,H,W = map(int,readline().split())
RCA = [int(x) for x in read().split()]
it = iter(RCA)
RCA = sorted(zip(it,it,it),key=operator.itemgetter(2),reverse=True)

root = list(range(H+W))
size = [0] * (H+W)
no_cycle = [True] * (H+W)

def find_root(x):
    y = root[x]
    if x == y:
        return y
    z = find_root(y)
    root[x] = z
    return z

def merge(x,y):
    x,y = find_root(x),find_root(y)
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    no_cycle[x] = no_cycle[x] and no_cycle[y]

answer = 0
for R,C,A in RCA:
    x,y = R-1,H+C-1
    rx,ry = find_root(x),find_root(y)
    assert 0 <= rx < H+W
    assert 0 <= ry < H+W
    continue
    if rx == ry:
        if not no_cycle[rx]:
            continue
        no_cycle[rx] = False
    else:
        if (not no_cycle[rx]) and (not no_cycle[ry]):
            continue
        merge(rx,ry)
    answer += A

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import operator

N,H,W = map(int,readline().split())
RCA = [int(x) for x in read().split()]
it = iter(RCA)
RCA = sorted(zip(it,it,it),key=operator.itemgetter(2),reverse=True)

root = list(range(H+W))
size = [0] * (H+W)
no_cycle = [True] * (H+W)

def find_root(x):
    y = root[x]
    if x == y:
        return y
    z = find_root(y)
    root[x] = z
    return z

def merge(x,y):
    x,y = find_root(x),find_root(y)
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    no_cycle[x] = no_cycle[x] and no_cycle[y]

answer = 0
for R,C,A in RCA:
    x,y = R-1,H+C-1
    assert 0 <= x < H+W
    assert 0 <= y < H+W
    continue
    rx,ry = find_root(x),find_root(y)
    if rx == ry:
        if not no_cycle[rx]:
            continue
        no_cycle[rx] = False
    else:
        if (not no_cycle[rx]) and (not no_cycle[ry]):
            continue
        merge(rx,ry)
    answer += A

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import operator

N,H,W = map(int,readline().split())
RCA = [int(x) for x in read().split()]
it = iter(RCA)
RCA = sorted(zip(it,it,it),key=operator.itemgetter(2),reverse=True)

root = list(range(H+W))
size = [0] * (H+W)
no_cycle = [True] * (H+W)

def find_root(x):
    y = root[x]
    if x == y:
        return y
    z = find_root(y)
    root[x] = z
    return z

def merge(x,y):
    x,y = find_root(x),find_root(y)
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    no_cycle[x] = no_cycle[x] and no_cycle[y]

answer = 0
for R,C,A in RCA:
    continue
    x,y = R-1,H+C-1
    rx,ry = find_root(x),find_root(y)
    if rx == ry:
        if not no_cycle[rx]:
            continue
        no_cycle[rx] = False
    else:
        if (not no_cycle[rx]) and (not no_cycle[ry]):
            continue
        merge(rx,ry)
    answer += A

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import operator

N,H,W = map(int,readline().split())
RCA = [int(x) for x in read().split()]
it = iter(RCA)
RCA = sorted(zip(it,it,it),key=operator.itemgetter(2),reverse=True)

Submission status: Wrong Answer

Solution code:
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
                new_root = r1
            else:
                self.table[r1] = r2
                self.table[r2] += d1
                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
cnt = 0

for a, r, c in cards:
    if uft.union(r, c):
        ans += a
        cnt += 1
        if cnt >= hw:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
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)  # 親(parent)と深さ(depth)。0以上は親。負の場合、そのノードが根で絶対値が深さ。
    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()

Submission status: Wrong Answer

Solution code:
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.size[uf.par[r]]+uf.size[uf.par[c]]==uf.Ecnt[uf.par[r]]+uf.Ecnt[uf.par[c]]:
        continue
    uf.union(r,c)
    ans+=a
print(ans)

Submission status: Wrong Answer

Solution code:
N, H, W = map(int, input().split())
r=[]
c=[]
w=[]
tmp = []
for num in range(N):
    a1, a2, a3=map(int, input().split())
    r.append(a1)
    c.append(a2)
    w.append(a3)

count=0
for num in range(N):
    tmp_list = [u for s, t, u in zip(r,c,w) if s == num]
    if tmp_list == []:
        continue
    max_r = max(tmp_list)
    if tmp_list.count(max_r) > 1:
        indexes = [i for i,u in enumerate(tmp_list) if u == max_r]
        
        cs = [t for i,t in enumerate(c) if i in indexes]
        ws = [u for s,t,u in zip(r,c,w) if t in cs and s == num]
        index_1 = ws.index(max(ws) )
    else:
        index_1 = tmp_list.index(max_r)
    w[index_1] = 0
    count += max_r

tmp_r = r
r = c
c = tmp_r
for num in range(N):
    tmp_list = [u for s, t, u in zip(r,c,w) if s == num]
    if tmp_list == []:
        continue
    max_r = max(tmp_list)
    if tmp_list.count(max_r) > 1:
        indexes = [i for i,u in enumerate(tmp_list) if u == max_r]
        
        cs = [t for i,t in enumerate(c) if i in indexes]
        ws = [u for s,t,u in zip(r,c,w) if t in cs and s == num]
        index_1 = ws.index(max(ws) )
    else:
        index_1 = tmp_list.index(max_r)
    w[index_1] = 0
    count += max_r

print(count)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, H, W = map(int, input().split())


    row = [[] for _ in range(H)]
    col = [[] for _ in range(W)]

    for _ in range(N):
        r, c, a = map(int ,input().split())
        r -= 1
        c -= 1
        heapq.heappush(row[r], (-a, c))
        heapq.heappush(col[c], (-a, r))

    ans = 0
    taken = set()
    for r in range(H):
        while row[r]:
            val, c = heapq.heappop(row[r])
            if not (r, c) in taken:
                ans -= val
                taken.add((r, c))
                break

    for c in range(W):
        while col[c]:
            val, r = heapq.heappop(col[c])
            if not (r, c) in taken:
                ans -= val
                taken.add((r, c))
                break

    print(ans)

sol()

Submission status: Wrong Answer

Solution code:
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, H, W = map(int, input().split())
    R, C = [None] * H, [None] * W

    for i in range(N):
        r, c, a = map(int, input().split())
        if R[r-1] == None: 
            R[r-1] = []
            heapq.heapify(R[r-1])
        if C[c-1] == None:
            C[c-1] = []
            heapq.heapify(C[c-1])
        heapq.heappush(R[r-1], (-a, r-1, c-1, i))
        heapq.heappush(C[c-1], (-a, r-1, c-1, i))
    #print(R)
    #print(C)
    ans = 0
    used = set()
    for j in range(H):
        if R[j]:
            point, r, c, i = heapq.heappop(R[j])
            ans += point
            used |= {(point, r, c, i)}

    for j in range(W):
        #print(j)
        #print(C[j])
        if C[j] != None:
            while C[j]:
                point, r, c, i = heapq.heappop(C[j])
                if (point, r, c, i) not in used:
                    ans += point
                    break
    print(-1 * ans)



    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import heapq
N, H, W = map(int, input().split())
A = [0] * N
HQ = [[] for _ in range(H)]
HL = [[0, i, 0] for i in range(H)]
WQ = [[] for _ in range(W)]
WL = [[0, i, 1] for i in range(W)]
for i in range(N):
  r, c, a = map(int, input().split())
  heapq.heappush(HQ[r - 1], [-a, i])
  HL[r - 1][0] += 1
  heapq.heappush(WQ[c - 1], [-a, i])
  WL[c - 1][0] += 1
cnt = 0
Q = []
for hl in HL:
  heapq.heappush(Q, hl)
for wl in WL:
  heapq.heappush(Q, wl)
while Q:
  _, i, s = heapq.heappop(Q)
  if s == 0:
    while HQ[i]:
      a, j = heapq.heappop(HQ[i])
      if A[j] == 0:
        cnt += -a
        A[j] = 1
        break
  else:
    while WQ[i]:
      a, j = heapq.heappop(WQ[i])
      if A[j] == 0:
        cnt += -a
        A[j] = 1
        break
print(cnt)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

n, h, w = map(int, input().split())
info = []
row_pq = [[] for i in range(h)]
col_pq = [[] for i in range(w)]
for i in range(n):
    r, c, a = map(int, input().split())
    info.append((r-1, c-1, a))
    heappush(row_pq[r-1], (-a, i))
    heappush(col_pq[c-1], (-a, i))

cards = set()
ans = 0
for i in range(h):
    while row_pq[i]:
        a, idx = heappop(row_pq[i])
        a *= -1
        if len(col_pq[info[idx][1]]) == 1:
            continue

        if idx not in cards:
            cards.add(idx)
            # print("row", i, a, idx)
            ans += a
            break

for j in range(w):
    while col_pq[j]:
        a, idx = heappop(col_pq[j])
        a *= -1
        if idx not in cards:
            cards.add(idx)
            ans += a
            # print("col", j, a, idx)
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from heapq import *
def min_cost_flow_dijkstra(E, s, t, f):
    INF = 1<<100
    NN = T + 1
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    h = [0] * NN
    res = 0
    while f > 0:
        dist = [INF] * NN
        dist[s] = 0
        q = []
        heappush(q, (0, s))
        while q:
            di, v = q.pop()
            if dist[v] < di: continue
            for i, (b, _cap, c, r) in enumerate(G[v]):
                if _cap > 0 and dist[b] > dist[v] + c + h[v] - h[b]:
                    dist[b] = dist[v] + c + h[v] - h[b]
                    prevv[b] = v
                    preve[b] = i
                    heappush(q, (dist[b], b))
        
        
        if dist[t] == INF:
            return -1
        for v in range(NN):
            h[v] += dist[v]
        
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * h[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

E = []
inf = 1 << 17
N, H, W = map(int, input().split())
S, T = H+W+N, H+W+N+1
for i in range(H):
    E.append((S, i, 1, 0))
for i in range(W):
    E.append((S, H+i, 1, 0))
for i in range(N):
    r, c, a = map(int, input().split())
    r -= 1
    c -= 1
    E.append((r, H+W+i, 1, 0))
    E.append((H+c, H+W+i, 1, 0))
    E.append((H+W+i, T, 1, inf - a))

E.append((S, T, H+W, inf))
print(inf * (H+W) - min_cost_flow_dijkstra(E, S, T, H+W))

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
def min_cost_flow_dijkstra(E, s, t, f):
    INF = 1<<100
    NN = T + 1
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    h = [0] * NN
    res = 0
    while f > 0:
        dist = [INF] * NN
        dist[s] = 0
        q = []
        heappush(q, (0, s))
        while q:
            di, v = q.pop()
            if dist[v] < di: continue
            for i, (b, _cap, c, r) in enumerate(G[v]):
                if _cap > 0 and dist[b] > dist[v] + c + h[v] - h[b]:
                    dist[b] = dist[v] + c + h[v] - h[b]
                    prevv[b] = v
                    preve[b] = i
                    heappush(q, (dist[b], b))
        
        
        if dist[t] == INF:
            return -1
        for v in range(NN):
            h[v] += dist[v]
        
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * h[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

E = []
inf = 1 << 17
N, H, W = map(int, input().split())
S, T = H+W+N, H+W+N+1
for i in range(H):
    E.append((S, i, 1, 0))
for i in range(W):
    E.append((S, H+i, 1, 0))
for i in range(N):
    r, c, a = map(int, input().split())
    r -= 1
    c -= 1
    E.append((r, H+W+i, 1, 0))
    E.append((H+c, H+W+i, 1, 0))
    E.append((H+W+i, T, 1, inf - a))

E.append((S, T, H+W, inf))
print(inf * (H+W) - min_cost_flow_dijkstra(E, S, T, H+W))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def min_cost_flow(E, s, t, f):
    INF = 1<<100
    NN = T+1
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    res = 0
    while f > 0:
        dist = [INF] * NN
        dist[s] = 0
        update = 1
        while update:
            update = 0
            for v in range(NN):
                if dist[v] == INF: continue
                for i, (b, _cap, c, r) in enumerate(G[v]):
                    if _cap > 0 and dist[b] > dist[v] + c:
                        dist[b] = dist[v] + c
                        prevv[b] = v
                        preve[b] = i
                        update = 1
        
        if dist[t] == INF:
            return -1

        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * dist[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    
    return res

E = []
inf = 1 << 17
N, H, W = map(int, input().split())
S, T = H+W+N, H+W+N+1
for i in range(H):
    E.append((S, i, 1, 0))
for i in range(W):
    E.append((S, H+i, 1, 0))
for i in range(N):
    r, c, a = map(int, input().split())
    r -= 1
    c -= 1
    E.append((r, H+W+i, 1, 0))
    E.append((H+c, H+W+i, 1, 0))
    E.append((H+W+i, T, 1, inf - a))

E.append((S, T, H+W, inf))
print(inf * (H+W) - min_cost_flow(E, S, T, H+W))

Submission status: Time Limit Exceeded

Solution code:
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)  # 親(parent)と深さ(depth)。0以上は親。負の場合、そのノードが根で絶対値が深さ。
    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:
            pd[gr] = 0
        else:
            merge(gr, gc)
        ans -= a
        cnt -= 1
    print(ans)

main()

Submission status: Time Limit Exceeded

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

def par(a):
    if P[a] == a: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) != par(b): C[par(a)] += C[par(b)]
    P[par(b)] = par(a)

N, H, W = map(int, input().split())
P = [i 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)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def par(a):
    if P[a] == a: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) != par(b): C[par(a)] += C[par(b)]
    P[par(b)] = par(a)

N, H, W = map(int, input().split())
P = [i 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)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,h,w = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    r,c,a = list(map(int, input().split()))
    r -= 1; c -= 1
    c += h
    ns[r].append((a,c))
    ns[c].append((a,r))
class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n
        self.es = [0]*n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            self.es[ri] += 1
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
            self.es[rj] += self.es[ri] + 1
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]
            self.es[ri] += self.es[rj] + 1

def selectEdge(ns):
    """各頂点に1本以下の接続枝を割り当てて、重み最大化
    """
    from heapq import heappop as hpp, heappush as hp
    q = []
    for u in ns.keys():
        for a,v in ns[u]:
            if u<v:
                hp(q, (-a,(u,v)))
    # 辺を選択できる = 選択した場合の連結成分において頂点数>=枝数
    uf = UnionFindTree(h+w)
    ans = 0
    while q:
        a, (u,v) = hpp(q)
        a *= -1
        ru = uf.root(u)
        rv = uf.root(v)
        if ru==rv and uf.es[ru]<uf.size[ru]:
            uf.connect(u,v)
            ans += a
        elif ru!=rv and (uf.es[ru]+uf.es[rv]+1) <= (uf.size[ru]+uf.size[rv]):
            uf.connect(u,v)
            ans += a
    return ans,uf
ans,uf = selectEdge(ns)
print(ans)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self._edge = [0] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy:
            self._edge[gx] += 1
            return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
            self._edge[gy] += self._edge[gx]+1
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]
            self._edge[gx] += self._edge[gy]+1

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

    def check(self,x,y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx==gy:
            return  self._size[gx]>=self._edge[gx]+1
        else:
            nv=self._size[gx]+self._size[gy]
            ne=self._edge[gx]+self._edge[gy]+1
            return nv>=ne

import sys

input=sys.stdin.readline

N,H,W=map(int,input().split())
card=[]
for i in range(N):
    r,c,a=map(int,input().split())
    card.append((a,r-1,c-1))

card.sort()

uf=UnionFindVerSize(H+W)
ans=0
while card:
    val,r,c=card.pop()
    if uf.check(r,H+c):
        uf.unite(r,H+c)
        ans+=val

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

class UF():
    def __init__(self, num):
        self.par = [-1]*num
        self.comp = [False]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            stack = []
            while self.par[x] >= 0:
                stack.append(x)
                x = self.par[x]
            for xi in stack:
                self.par[xi] = x
            return x
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.comp[rx] and self.comp[ry]:
                return False
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
            self.comp[rx] |= self.comp[ry]
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
            return True
        elif not self.comp[rx]:
            self.comp[rx] = True
            return True
        return False


N, H, W = map(int, readline().split())

geta = 10**5

Edge = []
for _ in range(N):
    h, w, a = map(int, readline().split())
    h -= 1
    w -= 1
    Edge.append((a, h, geta+w))

Edge.sort(reverse = True)

T = UF(2*geta)

ans = 0
for cost, a, b in Edge:
    if T.union(a, b):
        ans += cost
print(ans)

Submission status: Accepted

Solution code:

def wantp(x):

    wpq = []
    while p[x] != x:
        wpq.append(x)
        x = p[x]

    for i in wpq:
        p[i] = x

    return x


N,H,W = map(int,input().split())

ans = 0
ARC = []

for i in range(N):

    r,c,a = map(int,input().split())

    ARC.append([a,r-1,c-1])

ARC.sort()
ARC.reverse()

huse = [-1] * H
wuse = [-1] * W

p = [i for i in range(N)]
lnum = [0] * N
rank = [1] * N

for i in range(N):

    na = ARC[i][0]
    nr = ARC[i][1]
    nc = ARC[i][2]

    nowp = wantp(i)
    if huse[nr] == -1:
        lnum[nowp] += 1
        huse[nr] = nowp

    else:
        hp = wantp(huse[nr])

        if hp != nowp:

            if rank[hp] > rank[nowp]:
                p[nowp] = hp
                lnum[hp] += lnum[nowp]

            elif rank[hp] < rank[nowp]:
                p[hp] = nowp
                lnum[nowp] += lnum[hp]

            else:
                p[hp] = nowp
                lnum[nowp] += lnum[hp]
                rank[nowp] += 1


    nowp = wantp(i)
    if wuse[nc] == -1:
        lnum[nowp] += 1
        wuse[nc] = nowp

    else:
        wp = wantp(wuse[nc])

        if wp != nowp:

            if rank[wp] > rank[nowp]:
                p[nowp] = wp
                lnum[wp] += lnum[nowp]

            elif rank[wp] < rank[nowp]:
                p[wp] = nowp
                lnum[nowp] += lnum[wp]

            else:
                p[wp] = nowp
                lnum[nowp] += lnum[wp]
                rank[nowp] += 1

    
    nowp = wantp(i)
    if lnum[nowp] > 0:
          ans += na
          lnum[nowp] -= 1

print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        self.cycle = [0] * n
        self.group_num = 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 is_same(self, x, y):
        return self.root(x) == self.root(y)

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

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            self.cycle[r1] += self.cycle[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
            self.cycle[r2] += self.cycle[r1]
        self.group_num -= 1


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

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


n, h, w = LI()
uf = UnionFind(h + w)
ans = 0
rca = sorted(LIR(n), key=lambda x:x[2], reverse=True)
for r, c, a in rca:
    r -= 1; c -= 1
    if uf.is_same(r, h + c):
        if uf.get_cycle(r):
            continue
        else:
            uf.add_cycle(r)
            ans += a
    else:
        if uf.get_cycle(uf.root(r)) and uf.get_cycle(uf.root(h + c)):
            continue
        else:
            uf.unite(r, h + c)
            ans += a


print(ans)