Problem:


C : Pruning / 枝刈り

Problem

とにかくあつい。あづい君の住んでいる地域は今年猛暑であった。 さらに、家の庭には 1 本の木が生えており、毎日やかましく鳴く蝉が暑さを増幅させているような気がする。

庭の木は、まさにグラフ理論でいうところの木のような形をしており、この木にはたくさんの蝉が止まっている。
蝉は、必ず枝の先端(葉)または枝の分かれ目(頂点)に止まる習性がある。 ただし、木の根には 1 匹も止まることはない。
この木のある枝(辺)を切ると、それより空側(根と反対側)にいる蝉を全て駆除することができる。
ただし、枝を切るためには、その枝に応じた労力が必要となる。

(注 : 括弧内の言葉はグラフ理論の言葉で置き換えたものである。以降は全てグラフ理論の言葉で表現することにする。)

高度情報化社会となった現代においては、 部屋に居ながらにして頂点に何匹の蝉がいるか、 そして各辺を切るのに要する労力を調べることが出来る。

あづい君はその情報を用いて、 木に止まっている全ての蝉を駆除するのに必要な最小の労力を調べるプログラムを書くことにした。

Input

入力は次のような形式で与えられる．

N
C1 ... CN-1
u0 v0 p0
...
uN-2 vN-2 pN-2

N は木に含まれる頂点の数である。 各頂点には 0 ... N - 1 の番号が振られ、0番目の頂点を根とする。 C1 ... CN-1 は、各頂点に止まっている蝉の数であり、 Ci が i 番目の頂点に止まっている蝉の数である。 根には、蝉は1匹も止まっていない。 2 + i 行目の ui, vi, pi は、木に含まれる辺の情報である。ui, vi は辺が結ぶ 2 頂点の番号であり、pi はこの辺を切るのに必要な労力である。

Constraints

入力は全て整数である。

与えられるグラフは木である。

2 ≦ N ≦ 1,000

0 ≦ Ci ≦ 1,000

0 ≦ ui , vi N

1 ≦ pi ≦ 1,000

Output

蝉を全て駆除するために必要な最小の労力を 1 行で出力せよ。

Samples

Sample Input 1

5
2 2 2 2
0 1 4
1 2 1
1 3 1
1 4 1

Sample Output 1

4

頂点 0 と 1 をつなぐ辺を切れば、全ての蝉を駆除することができる。

Sample Input 2

5
0 2 2 2
0 1 4
1 2 1
1 3 1
1 4 1

Sample Output 2

3

頂点 1 と 2 、 1 と 3 、 1 と 4 をつなぐ辺の3本を切れば最小の労力で蝉を駆除することができる。 なお、頂点 0 と 1 をつなぐ辺を切ることで全ての蝉を駆除することができるが、これにはコストが 4 かかってしまう。


Sample input:
5
2 2 2 2
0 1 4
1 2 1
1 3 1
1 4 1


Sample output:
4

Submission status: Accepted

Solution code:
from collections import deque
import bisect

INF = float("inf")

N = int(input())
C = list(map(int, input().split()))
uvp = [list(map(int, input().split())) for i in range(N-1)]

edge = [[0]*(N+1) for i in range(N+1)]
utov = [[] for i in range(N+1)]

for u, v, p in uvp:
    edge[u][v] = edge[v][u] = p
    utov[u].append(v)
    utov[v].append(u)

for i in range(1, N):
    if (C[i-1] > 0):
        edge[i][N] = INF
        utov[i].append(N)
        utov[N].append(i)


def bfs(s, g, n):
    bfs_map = [-1]*n
    bfs_map[s] = 0
    q = deque()
    q.append(s)

    while q:
        u = q.popleft()
        for v in utov[u]:
            if (edge[u][v] > 0) and (bfs_map[v] < 0):
                bfs_map[v] = bfs_map[u] + 1
                q.append(v)

    return bfs_map

def update(s, g, bfs_map):
    f = INF
    distance = bfs_map[g]
    p = [[None, None] for i in range(distance)]
    y = g
    for i in range(distance)[::-1]:
        p[i][1] = y
        for x in utov[y]:
            if (edge[x][y] > 0) and (bfs_map[x] == i):
                if (edge[x][y] < f):
                    f = edge[x][y]
                y = x
                p[i][0] = x
                break
        else:
            return 0
    for x,y in p:
        edge[x][y] -= f
        edge[y][x] += f
    return f

def dinic(s, g, n):
    max_flow = 0
    while True:
        bfs_map = bfs(s, g, n)
        if (bfs_map[g] < 0):
            return max_flow
        cap = update(s, g, bfs_map)
        while (cap > 0):
            max_flow += cap
            cap = update(s, g, bfs_map)

print(dinic(0, N, N+1))

Submission status: Accepted

Solution code:
import sys
from collections import deque
def bfs(s,g,n):
    bfs_map = [-1]*n
    bfs_map[s] = 0
    q = deque([s])
    while q:
        x = q.popleft()
        for y in v[x]:
            for y in v[x]:
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    q.append(y)
    return bfs_map

def update(s,g,bfs_map):
    f = float("inf")
    p = [[None]*2 for i in range(bfs_map[g])]
    y = g
    for i in range(bfs_map[g])[::-1]:
        p[i][1] = y
        for x in v[y]:
            if c[x][y] > 0 and bfs_map[x] == i:
                if c[x][y] < f:
                    f = c[x][y]
                y = x
                p[i][0] = x
                break
        else:
            return 0
    for x,y in p:
        c[x][y] -= f
        c[y][x] += f
    return f

def dinic(s,g,n):
    f = 0
    while 1:
        bfs_map = bfs(s,g,n)
        if bfs_map[g] < 0:
            return f
        cap = update(s,g,bfs_map)
        while cap > 0:
            f += cap
            cap = update(s,g,bfs_map)

n = int(sys.stdin.readline())
d = [int(x) for x in sys.stdin.readline().split()]
c = [[0]*(n+1) for i in range(n+1)]
v = [[] for i in range(n+1)]
for i in range(1,n):
    if d[i-1] > 0:
        v[i].append(n)
        v[n].append(i)
        c[i][n] = float("inf")

for i in range(n-1):
    a,b,p = [int(x) for x in sys.stdin.readline().split()]
    v[a].append(b)
    v[b].append(a)
    c[a][b] = p
    c[b][a] = p

print(dinic(0,n,n+1))

Submission status: Accepted

Solution code:
n = int(input())
c_lst = [0] + list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n - 1):
  u, v, p = map(int, input().split())
  edges[u].append((v, p))
  edges[v].append((u, p))

INF = 10 ** 20
used = [False] * n
def cost(x):
  used[x] = True
  ret = 0
  pre_cost = 0 if x != 0 else INF
  for to, p in edges[x]:
    if used[to]:pre_cost = p
    else:
      ret += cost(to)
  if c_lst[x] == 0:return min(ret, pre_cost)
  else:return pre_cost

print(cost(0))