Problem:


C : Shopping / 買い物

問題文

料理が得意な2D君は昼ごはんを作ろうとしている。料理には N 個の材料 a_{0}, a_{1}, … , a_{N&minus;1} が全てが必要である。

さて、今2D君の家の冷蔵庫には一つも材料が入っていないので、スーパーに買いに行かなければならない。スーパーでは材料 a_{i} を値段 x_{i} 円で買うことができる。

2D君は魔法使いでもあり、 M 種類の魔法が使える。 i 番目の魔法を材料 s_{i} にかければ材料 t_{i} に、また逆に t_{i} にかければ s_{i} に変えることができる。さらに、一つの材料に対して複数の魔法を繰り返して使うことができる。例えば、 p から q に変える魔法と、 q から r に変える魔法の2つを使って、 p から r を得ることができる。

2D君は魔法の力を借りてなるべく安く材料を揃えることにした。料理を完成させるために2D君が買う必要のある材料の、値段の総和の最小値を求めよ。

入力

入力は以下の形式で与えられる。

N
a_{0} x_{0}
…
a_{N&minus;1} x_{N&minus;1}
M
s_{0} t_{0}
…
s_{M&minus;1} t_{M&minus;1}

制約

数値はすべて整数である

材料の名前はすべて 1 文字以上 10 文字以下のアルファベット小文字からなる

i ≠ j なら a_{i} ≠ a_{j}

1 \≤ x_{i} \≤ 1,000

1 \≤ N \≤ 5,000

0 \≤ M \≤ {\rm min}(N(N&minus;1)/2, 1000)

s_{i} ≠ t_{i}

s_{i},t_{i} の組に重複はない

s_{i},t_{i} は a_{0},…,a_{N&minus;1} に含まれる

出力

答えを1行で出力せよ。

サンプル

サンプル入力1

2
tako 2
yaki 1
1
tako yaki

魔法によって安い yaki を tako に変えることができるので、 yaki を 2 個買えばよい。

サンプル出力1

2

サンプル入力2

5
a 1
b 2
c 2
d 4
e 3
5
b a
a c
c d
e b
c b

サンプル出力2

5

下に示すように、全ての材料を a から変えてそろえることができる。

a : a そのまま

b : a -> c -> b

c : a -> c

d : a -> c -> d

e : a -> b -> e



Sample input:
2
tako 2
yaki 1
1
tako yaki


Sample output:
2

Submission status: Accepted

Solution code:
inf = 10**9
par = [0]*5001
rank = [0]*5001
def init_union_find(V):
    for i in xrange(V):
        par[i] = i
        rank[i] = 0
        
def find(x):
    if par[x] == x: return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def unite(x,y):
    x = find(x)
    y = find(y)
    if (x == y): return
    
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if(rank[x] == rank[y]): rank[x] += 1

def same(x,y):
    return find(x) == find(y)

N = int(raw_input())
init_union_find(N)
cost = [0]*N
dic = {}
for i in xrange(N):
    a,x = raw_input().split()
    dic[a] = i
    cost[i] = int(x)
    
M = int(raw_input())
for loop in xrange(M):
    s,t = raw_input().split()
    unite(dic[s],dic[t])

ans = 0
ncost = [inf]*N
for i,c in sorted(enumerate(cost), key = lambda a:a[1]):
    p = find(i)
    if ncost[p] == inf:
        ncost[p] = c
    ans += ncost[p]
print ans

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict,deque
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
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

f = defaultdict(int)
par = defaultdict(int)
rank = defaultdict(int)
n = int(sys.stdin.readline())
for i in range(n):
    a,x = sys.stdin.readline().split()
    f[a] = int(x)
    par[a] = a
    rank[a] = 0

m = int(sys.stdin.readline())
for i in range(m):
    x,y = sys.stdin.readline().split()
    if root(x) != root(y):
        unite(x,y)

ans = 0
for i in f.keys():
    root(i)
    f[par[i]] = min(f[par[i]],f[i])
for i in f.keys():
    ans += f[root(i)]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
dic = {}
price = []
for i in range(n):
  a, x = input().split()
  dic[a] = i
  price.append(int(x))

parent = [i for i in range(n)]

def find(x):
  if parent[x] == x:return x
  parent[x] = find(parent[x])
  return parent[x]

m = int(input())
for _ in range(m):
  s, t = input().split()
  si, ti = dic[s], dic[t]
  ps = find(si)
  pt = find(ti)
  parent[ps] = parent[pt]

groups = {}
for i in range(n):
  if find(i) in groups:
    min_price, cnt = groups[find(i)]
    groups[find(i)] = (min(min_price, price[i]), cnt + 1)
  else:
    groups[find(i)] = (price[i], 1)

print(sum([v[0] * v[1] for _, v in groups.items()]))