Petya and Graph (Codeforces 1082G)
Tags: Others, flows

Petya has a simple graph (that is, a graph without loops or multiple edges) consisting of $$$n$$$ vertices and $$$m$$$ edges.The weight of the $$$i$$$-th vertex is $$$a_i$$$.The weight of the $$$i$$$-th edge is $$$w_i$$$.A subgraph of a graph is some set of the graph vertices and some set of the graph edges. The set of edges must meet the condition: both ends of each edge from the set must belong to the chosen set of vertices. The weight of a subgraph is the sum of the weights of its edges, minus the sum of the weights of its vertices. You need to find the maximum weight of subgraph of given graph. The given graph does not contain loops and multiple edges.

Input: The first line contains two numbers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^3, 0 \le m \le 10^3$$$) - the number of vertices and edges in the graph, respectively.The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - the weights of the vertices of the graph.The following $$$m$$$ lines contain edges: the $$$i$$$-e edge is defined by a triple of integers $$$v_i, u_i, w_i$$$ ($$$1 \le v_i, u_i \le n, 1 \le w_i \le 10^9, v_i \neq u_i$$$). This triple means that between the vertices $$$v_i$$$ and $$$u_i$$$ there is an edge of weight $$$w_i$$$. It is guaranteed that the graph does not contain loops and multiple edges.

Output: Print one integer — the maximum weight of the subgraph of the given graph.

Note: In the first test example, the optimal subgraph consists of the vertices $$${1, 3, 4}$$$ and has weight $$$4 + 4 + 5 - (1 + 2 + 2) = 8$$$. In the second test case, the optimal subgraph is empty.

Sample Inputs:
4 5
1 5 2 2
1 3 4
1 4 4
3 4 5
3 2 2
4 2 2

3 3
9 7 8
1 2 1
2 3 2
1 3 3

Sample Outputs:
8

0

Solution (Python):
import sys
from collections import deque

class Edge:

    def __init__(self, to, w, next):
        self.to = to
        self.w = w
        self.next = next

def add(u, v, w):
    global idx
    idx += 1
    edges.append(Edge(v, w, head[u]))
    head[u] = idx

def add_edge(u, v, w):
    add(u, v, w)
    add(v, u, 0)

def bfs():
    global dist
    dist = [oo] * (t + 1)
    q = deque()
    q.append(s)
    dist[s] = 0
    while q:
        u = q.popleft()
        idx = head[u]
        while idx:
            v = edges[idx].to
            if dist[v] == oo and edges[idx].w != 0:
                dist[v] = dist[u] + 1
                q.append(v)
            idx = edges[idx].next
    return dist[t] != oo

def dfs(u, limit):
    global dist
    if u == t or limit == 0:
        return limit
    flow = 0
    idx = head[u]
    while idx:
        v = edges[idx].to
        if dist[v] == dist[u] + 1 and edges[idx].w != 0:
            aug = dfs(v, min(limit - flow, edges[idx].w))
            flow += aug
            edges[idx].w -= aug
            edges[idx ^ 1].w += aug
            if limit == flow:
                break
        idx = edges[idx].next
    if not flow:
        dist[u] = None
    return flow

def dinic():
    mf = 0
    while bfs():
        mf += dfs(s, oo)
    return mf
(n, m) = map(int, sys.stdin.readline().split())
weight_sum = 0
weight = [None] + list(map(int, sys.stdin.readline().split()))
edges = [None, None]
idx = 1
s = n + m + 1
t = s + 1
head = [0] * (t + 1)
oo = float('inf')
for i in range(1, n + 1):
    add_edge(s, i, weight[i])
for i in range(1, m + 1):
    (u, v, w) = map(int, sys.stdin.readline().split())
    add_edge(n + i, t, w)
    add_edge(u, n + i, oo)
    add_edge(v, n + i, oo)
    weight_sum += w
weight_sum -= dinic()
print(weight_sum)

Solution (Python):
class edge(object):

    def __init__(self, ne, to, fl):
        self.ne = ne
        self.to = to
        self.fl = fl

def add(x, y, z):
    global tot
    tot += 1
    e.append(edge(he[x], y, z))
    he[x] = tot

def addedge(x, y, z):
    add(x, y, z)
    add(y, x, 0)

def bfs():
    global deep
    deep = [0 for i in range(T + 1)]
    q = []
    q.append(S)
    deep[S] = 1
    lp = 0
    while len(q) > lp:
        x = q[lp]
        lp += 1
        i = he[x]
        while i:
            y = e[i].to
            if deep[y] == 0 and e[i].fl != 0:
                deep[y] = deep[x] + 1
                q.append(y)
            i = e[i].ne
    return deep[T] != 0

def dfs(x, flow):
    global deep
    if x == T or flow == 0:
        return flow
    used = 0
    i = he[x]
    while i:
        y = e[i].to
        if deep[y] == deep[x] + 1 and e[i].fl != 0:
            now = dfs(y, min(flow - used, e[i].fl))
            used += now
            e[i].fl -= now
            e[i ^ 1].fl += now
            if flow == used:
                break
        i = e[i].ne
    if used == 0:
        deep[x] = -1
    return used

def dinic():
    res = 0
    while bfs():
        res += dfs(S, INF)
    return res
(n, m) = map(int, input().split())
ans = 0
weight = [0] + list(map(int, input().split()))
e = [0, 0]
tot = 1
S = n + m + 1
T = S + 1
he = [0 for i in range(T + 1)]
INF = 1000000007
for i in range(1, n + 1):
    addedge(S, i, weight[i])
for i in range(1, m + 1):
    (x, y, w) = map(int, input().split())
    addedge(n + i, T, w)
    addedge(x, n + i, INF)
    addedge(y, n + i, INF)
    ans += w
ans -= dinic()
print(ans)

Solution (Python):
class edge(object):

    def __init__(self, ne, to, fl):
        self.ne = ne
        self.to = to
        self.fl = fl

def add(x, y, z):
    global tot
    tot += 1
    e.append(edge(he[x], y, z))
    he[x] = tot

def addedge(x, y, z):
    add(x, y, z)
    add(y, x, 0)

def bfs():
    global deep
    deep = [0 for i in range(T + 1)]
    q = []
    q.append(S)
    deep[S] = 1
    while len(q) > 0:
        x = q[0]
        del q[0]
        i = he[x]
        while i:
            y = e[i].to
            if deep[y] == 0 and e[i].fl != 0:
                deep[y] = deep[x] + 1
                q.append(y)
            i = e[i].ne
    return deep[T] != 0

def dfs(x, flow):
    global deep
    if x == T or flow == 0:
        return flow
    used = 0
    i = he[x]
    while i:
        y = e[i].to
        if deep[y] == deep[x] + 1 and e[i].fl != 0:
            now = dfs(y, min(flow - used, e[i].fl))
            used += now
            e[i].fl -= now
            e[i ^ 1].fl += now
            if flow == used:
                break
        i = e[i].ne
    if used == 0:
        deep[x] = -1
    return used

def dinic():
    res = 0
    while bfs():
        res += dfs(S, INF)
    return res
(n, m) = map(int, input().split())
ans = 0
weight = [0] + list(map(int, input().split()))
e = [0, 0]
tot = 1
S = n + m + 1
T = S + 1
he = [0 for i in range(T + 1)]
INF = 1000000007
for i in range(1, n + 1):
    addedge(S, i, weight[i])
for i in range(1, m + 1):
    (x, y, w) = map(int, input().split())
    addedge(n + i, T, w)
    addedge(x, n + i, INF)
    addedge(y, n + i, INF)
    ans += w
ans -= dinic()
print(ans)