Underfail (Codeforces 717G)
Tags: Others, flows

You have recently fallen through a hole and, after several hours of unconsciousness, have realized you are in an underground city. On one of your regular, daily walks through the unknown, you have encountered two unusually looking skeletons called Sanz and P’pairus, who decided to accompany you and give you some puzzles for seemingly unknown reasons.One day, Sanz has created a crossword for you. Not any kind of crossword, but a 1D crossword! You are given m words and a string of length n. You are also given an array p, which designates how much each word is worth — the i-th word is worth pi points. Whenever you find one of the m words in the string, you are given the corresponding number of points. Each position in the crossword can be used at most x times. A certain word can be counted at different places, but you cannot count the same appearance of a word multiple times. If a word is a substring of another word, you can count them both (presuming you haven’t used the positions more than x times).In order to solve the puzzle, you need to tell Sanz what’s the maximum achievable number of points in the crossword. There is no need to cover all postions, just get the maximal score! Crossword and words contain only lowercase English letters.

Input: The first line of the input contains a single integer n (1 ≤ n ≤ 500) — the length of the crossword. The second line contains the crossword string. The third line contains a single integer m (1 ≤ m ≤ 100) — the number of given words, and next m lines contain description of words: each line will have a string representing a non-empty word (its length doesn't exceed the length of the crossword) and integer pi (0 ≤ pi ≤ 100). Last line of the input will contain x (1 ≤ x ≤ 100) — maximum number of times a position in crossword can be used.

Output: Output single integer — maximum number of points you can get.

Note: For example, with the string "abacba", words "aba" (6 points) and "ba" (3 points), and x = 3, you can get at most 12 points - the word "aba" appears once ("abacba"), while "ba" appears two times ("abacba"). Note that for x = 1, you could get at most 9 points, since you wouldn’t be able to count both "aba" and the first appearance of "ba".

Sample Inputs:
6
abacba
2
aba 6
ba 3
3

Sample Outputs:
12

Solution (Python):
import sys
from heapq import heappop, heappush

class Edge:

    def __init__(self, u, v, cap, cost, rev):
        self.u = u
        self.v = v
        self.flow = 0
        self.cap = cap
        self.cost = cost
        self.rev = rev

def add_edge(adj, u, v, capv, costv):
    adj[u].append(Edge(u, v, capv, costv, len(adj[v])))
    adj[v].append(Edge(v, u, 0, -costv, len(adj[u]) - 1))

def match(crossword, cw_idx, word):
    for k in range(len(word)):
        if crossword[cw_idx + k] != word[k]:
            return False
    return True

def read_input():
    n = int(sys.stdin.readline())
    crossword = sys.stdin.readline()[:-1]
    m = int(sys.stdin.readline())
    adj = [[] for _ in range(n + 2)]
    for _ in range(m):
        (word, p) = sys.stdin.readline().split()
        p = int(p)
        i = 0
        while i + len(word) <= n:
            if match(crossword, i, word):
                (u, v) = (i + 1, i + 1 + len(word))
                add_edge(adj, u, v, 1, -p)
            i += 1
    x = int(sys.stdin.readline())
    for i in range(n + 1):
        (u, v) = (i, i + 1)
        add_edge(adj, u, v, x, 0)
    return adj

def bellman_ford(adj):
    potential = [0] * len(adj)
    for _ in range(len(adj)):
        for u in range(len(adj)):
            for e in adj[u]:
                reduced_cost = potential[e.u] + e.cost - potential[e.v]
                if e.cap > 0 and reduced_cost < 0:
                    potential[e.v] += reduced_cost
    return potential

def dijkstra(adj, potential, s, t):
    oo = float('inf')
    (dist, pi) = ([+oo] * len(adj), [None] * len(adj))
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        (du, u) = heappop(heap)
        if dist[u] < du:
            continue
        if u == t:
            break
        for e in adj[u]:
            reduced_cost = potential[e.u] + e.cost - potential[e.v]
            if e.cap - e.flow > 0 and dist[e.v] > dist[e.u] + reduced_cost:
                dist[e.v] = dist[e.u] + reduced_cost
                heappush(heap, (dist[e.v], e.v))
                pi[e.v] = e
    return (dist, pi)

def min_cost_max_flow(adj):
    (min_cost, max_flow) = (0, 0)
    oo = float('inf')
    potential = bellman_ford(adj)
    (s, t) = (0, len(adj) - 1)
    while True:
        (dist, pi) = dijkstra(adj, potential, s, t)
        if dist[t] == +oo:
            break
        for u in range(len(adj)):
            if dist[u] < dist[t]:
                potential[u] += dist[u] - dist[t]
        (limit, v) = (+oo, t)
        while v:
            e = pi[v]
            limit = min(limit, e.cap - e.flow)
            v = e.u
        v = t
        while v:
            e = pi[v]
            e.flow += limit
            adj[v][e.rev].flow -= limit
            v = e.u
        min_cost += limit * (potential[t] - potential[s])
        max_flow += limit
    return (min_cost, max_flow)
adj = read_input()
(min_cost, _) = min_cost_max_flow(adj)
print(-min_cost)

Solution (Python):
import sys
from heapq import heappop, heappush

class Edge:

    def __init__(self, u, v, cap, flow, cost, rev) -> None:
        self.u = u
        self.v = v
        self.cap = cap
        self.flow = flow
        self.cost = cost
        self.rev = rev

def add_edge(adj, u, v, capv, flowv, costv):
    if u == 6 and v == 7:
        foo = 0
    adj[u].append(Edge(u, v, capv, flowv, costv, len(adj[v])))
    adj[v].append(Edge(v, u, 0, flowv, -costv, len(adj[u]) - 1))

def match(crossword, cw_idx, word):
    for k in range(len(word)):
        if crossword[cw_idx + k] != word[k]:
            return False
    return True

def read_input():
    """"""
    n = int(sys.stdin.readline())
    crossword = sys.stdin.readline()[:-1]
    m = int(sys.stdin.readline())
    adj = [[] for _ in range(n + 2)]
    m_words = ['aba 6\n', 'ba 3\n', 'bac 4\n', 'cb 3\n', 'c 6']
    for idx in range(m):
        (word, p) = sys.stdin.readline().split()
        p = int(p)
        i = 0
        while i + len(word) <= n:
            if match(crossword, i, word):
                (u, v) = (i + 1, i + 1 + len(word))
                add_edge(adj, u, v, 1, 0, -p)
            i += 1
    x = int(sys.stdin.readline())
    for i in range(n + 1):
        (u, v) = (i, i + 1)
        add_edge(adj, u, v, x, 0, 0)
    return adj

def bellman_ford(adj, potencial):
    for _ in range(len(adj)):
        for u in range(len(adj)):
            for e in adj[u]:
                reduced_cost = potencial[e.u] + e.cost - potencial[e.v]
                if e.cap > 0 and reduced_cost < 0:
                    potencial[e.v] += reduced_cost

def dijkstra(adj, potencial, dist, pi, s, t):
    oo = float('inf')
    for u in range(len(adj)):
        dist[u] = +oo
        pi[u] = None
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        (du, u) = heappop(heap)
        if dist[u] < du:
            continue
        if u == t:
            break
        for e in adj[u]:
            reduced_cost = potencial[e.u] + e.cost - potencial[e.v]
            if e.flow < e.cap and dist[e.v] > dist[e.u] + reduced_cost:
                dist[e.v] = dist[e.u] + reduced_cost
                heappush(heap, (dist[e.v], e.v))
                pi[e.v] = e

def min_cost_max_flow(adj):
    (min_cost, max_flow) = (0, 0)
    (potencial, oo) = ([0] * len(adj), float('inf'))
    (dist, pi) = ([+oo] * len(adj), [None] * len(adj))
    bellman_ford(adj, potencial)
    (s, t) = (0, len(adj) - 1)
    while True:
        dijkstra(adj, potencial, dist, pi, s, t)
        if dist[t] == +oo:
            break
        for u in range(len(adj)):
            if dist[u] < dist[t]:
                potencial[u] += dist[u] - dist[t]
        (limit, v) = (+oo, t)
        while v:
            e = pi[v]
            limit = min(limit, e.cap - e.flow)
            v = e.u
        v = t
        while v:
            e = pi[v]
            e.flow += limit
            try:
                adj[v][e.rev].flow -= limit
            except:
                adj[v][e.rev].flow -= limit
            v = e.u
        min_cost += limit * (potencial[t] - potencial[s])
        max_flow += limit
    return (min_cost, max_flow)
adj = read_input()
(min_cost, _) = min_cost_max_flow(adj)
print(-min_cost)

Solution (Python):
import sys
from heapq import heappop, heappush

class Edge:

    def __init__(self, u, v, cap, flow, cost, rev) -> None:
        self.u = u
        self.v = v
        self.cap = cap
        self.flow = flow
        self.cost = cost
        self.rev = rev

def add_edge(adj, u, v, capv, flowv, costv):
    if u == 6 and v == 7:
        foo = 0
    adj[u].append(Edge(u, v, capv, flowv, costv, len(adj[v])))
    adj[v].append(Edge(v, u, 0, flowv, -costv, len(adj[u]) - 1))

def match(crossword, cw_idx, word):
    for k in range(len(word)):
        if crossword[cw_idx + k] != word[k]:
            return False
    return True

def read_input():
    """"""
    n = int(sys.stdin.readline())
    crossword = sys.stdin.readline()[:-1]
    m = int(sys.stdin.readline())
    adj = [[] for _ in range(n + 2)]
    m_words = ['aba 6\n', 'ba 3\n', 'bac 4\n', 'cb 3\n', 'c 6']
    for idx in range(m):
        (word, p) = sys.stdin.readline().split()
        p = int(p)
        i = 0
        while i + len(word) <= n:
            if match(crossword, i, word):
                (u, v) = (i + 1, i + 1 + len(word))
                add_edge(adj, u, v, 1, 0, -p)
            i += 1
    x = int(sys.stdin.readline())
    for i in range(n + 1):
        (u, v) = (i, i + 1)
        add_edge(adj, u, v, x, 0, 0)
    return adj

def bellman_ford(adj, potencial):
    for _ in range(len(adj)):
        for u in range(len(adj)):
            for e in adj[u]:
                reduced_cost = potencial[e.u] + e.cost - potencial[e.v]
                if e.cap > 0 and reduced_cost < 0:
                    potencial[e.v] += reduced_cost

def dijkstra(adj, potencial, dist, pi, s, t):
    oo = float('inf')
    for u in range(len(adj)):
        dist[u] = +oo
        pi[u] = None
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        (du, u) = heappop(heap)
        if dist[u] < du:
            continue
        if u == t:
            break
        for e in adj[u]:
            reduced_cost = potencial[e.u] + e.cost - potencial[e.v]
            if e.flow < e.cap and dist[e.v] > dist[e.u] + reduced_cost:
                dist[e.v] = dist[e.u] + reduced_cost
                heappush(heap, (dist[e.v], e.v))
                pi[e.v] = e

def min_cost_max_flow(adj):
    (min_cost, max_flow) = (0, 0)
    (potencial, oo) = ([0] * len(adj), float('inf'))
    (dist, pi) = ([+oo] * len(adj), [None] * len(adj))
    bellman_ford(adj, potencial)
    (s, t) = (0, len(adj) - 1)
    while True:
        dijkstra(adj, potencial, dist, pi, s, t)
        if dist[t] == +oo:
            break
        for u in range(len(adj)):
            if dist[u] < dist[t]:
                potencial[u] += dist[u] - dist[t]
        (limit, v) = (+oo, t)
        while v:
            e = pi[v]
            limit = min(limit, e.cap - e.flow)
            v = e.u
        v = t
        while v:
            e = pi[v]
            e.flow += limit
            try:
                adj[v][e.rev].flow -= limit
            except:
                adj[v][e.rev].flow -= limit
            v = e.u
        min_cost += limit * (potencial[t] - potencial[s])
        max_flow += limit
    return (min_cost, max_flow)
adj = read_input()
(min_cost, _) = min_cost_max_flow(adj)
print(-min_cost)