Problem:


Problem G: Concert Hall Scheduling

You are appointed director of a famous concert hall, to save it from bankruptcy. The hall is very
popular, and receives many requests to use its two fine rooms, but unfortunately the previous
director was not very efficient, and it has been losing money for many years. The two rooms are
of the same size and arrangement. Therefore, each applicant wishing to hold a concert asks for
a room without specifying which. Each room can be used for only one concert per day.

In order to make more money, you have decided to abandon the previous fixed price policy, and
rather let applicants specify the price they are ready to pay. Each application shall specify a
period [i, j] and an asking price w, where i and j are respectively the first and last days of the
period (1 ≤ i ≤ j ≤ 365), and w is a positive integer in yen, indicating the amount the applicant
is willing to pay to use a room for the whole period.

You have received applications for the next year, and you should now choose the applications
you will accept. Each application should be either accepted for its whole period or completely
rejected. Each concert should use the same room during the whole applied period.

Considering the dire economic situation of the concert hall, artistic quality is to be ignored,
and you should just try to maximize the total income for the whole year by accepting the most
profitable applications.

Input

The input has multiple data sets, each starting with a line consisting of a single integer n, the
number of applications in the data set. Then, it is followed by n lines, each of which represents
one application with a period [i, j] and an asking price w yen in the following format.

        i j w

A line containing a single zero indicates the end of the input.

The maximum number of applications in a data set is one thousand, and the maximum asking
price is one million yen.

Output

For each data set, print a single line containing an integer, the maximum total income in yen
for the data set.

Sample Input

4
1 2 10
2 3 10
3 3 10
1 3 10
6
1 20 1000
3 25 10000
5 15 5000
22 300 5500
10 295 9000
7 7 6000
8
32 251 2261
123 281 1339
211 235 5641
162 217 7273
22 139 7851
194 198 9190
119 274 878
122 173 8640
0

Output for the Sample Input

30
25500
38595



Sample input:
4
1 2 10
2 3 10
3 3 10
1 3 10
6
1 20 1000
3 25 10000
5 15 5000
22 300 5500
10 295 9000
7 7 6000
8
32 251 2261
123 281 1339
211 235 5641
162 217 7273
22 139 7851
194 198 9190
119 274 878
122 173 8640
0


Sample output:
30
25500
38595

Submission status: Accepted

Solution code:
import heapq


class MinCostFlow:
    class Edge:
        def __init__(self, to, cap, rev, cost):
            self.to, self.cap, self.rev, self.cost = to, cap, rev, cost

    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, fr, to, cap, cost):
        self.E[fr].append(self.Edge(to, cap, len(self.E[to]), cost))
        self.E[to].append(self.Edge(fr, 0, len(self.E[fr])-1, -cost))

    def run(self, source, sink, f, INF=10**5):
        res = 0
        h, prevv, preve = [0] * self.V, [0] * self.V, [0] * self.V
        while (f > 0):
            pque = []
            dist = [INF] * self.V
            dist[source] = 0
            heapq.heappush(pque, (0, source))
            while pque:
                cost, v = heapq.heappop(pque)
                cost = -cost
                if dist[v] < cost:
                    continue
                for i, e in enumerate(self.E[v]):
                    if e.cap > 0 and dist[v] - h[e.to] < dist[e.to] - e.cost - h[v]:
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]
                        prevv[e.to], preve[e.to] = v, i
                        heapq.heappush(pque, (-dist[e.to], e.to))
            if dist[sink] == INF:
                return -1
            for v in range(self.V):
                h[v] += dist[v]

            d, v = f, sink
            while v != source:
                d = min(d, self.E[prevv[v]][preve[v]].cap)
                v = prevv[v]
            f -= d
            res += d * h[sink]
            v = sink
            while v != source:
                self.E[prevv[v]][preve[v]].cap -= d
                self.E[v][self.E[prevv[v]][preve[v]].rev].cap += d
                v = prevv[v]
        return res


while True:
    N = int(input())
    if not N:
        break
    V = 366
    mcf = MinCostFlow(V)
    for i in range(V - 1):
        mcf.add_edge(i, i + 1, 2, 0)
    for _ in range(N):
        s, t, c = map(int, input().split())
        mcf.add_edge(s - 1, t, 1, -c)
    print(-mcf.run(0, V - 1, 2, 10 ** 9))

Submission status: Accepted

Solution code:
import heapq
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input


class MinCostFlow:
    class Edge:
        def __init__(self, to, cap, rev, cost):
            self.to, self.cap, self.rev, self.cost = to, cap, rev, cost

    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, fr, to, cap, cost):
        self.E[fr].append(self.Edge(to, cap, len(self.E[to]), cost))
        self.E[to].append(self.Edge(fr, 0, len(self.E[fr])-1, -cost))

    def run(self, source, sink, f, INF=10**5):
        res = 0
        h, prevv, preve = [0] * self.V, [0] * self.V, [0] * self.V
        while (f > 0):
            pque = []
            dist = [INF] * self.V
            dist[source] = 0
            heapq.heappush(pque, (0, source))
            while pque:
                cost, v = heapq.heappop(pque)
                cost = -cost
                if dist[v] < cost:
                    continue
                for i, e in enumerate(self.E[v]):
                    if e.cap > 0 and dist[v] - h[e.to] < dist[e.to] - e.cost - h[v]:
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]
                        prevv[e.to], preve[e.to] = v, i
                        heapq.heappush(pque, (-dist[e.to], e.to))
            if dist[sink] == INF:
                return -1
            for v in range(self.V):
                h[v] += dist[v]

            d, v = f, sink
            while v != source:
                d = min(d, self.E[prevv[v]][preve[v]].cap)
                v = prevv[v]
            f -= d
            res += d * h[sink]
            v = sink
            while v != source:
                self.E[prevv[v]][preve[v]].cap -= d
                self.E[v][self.E[prevv[v]][preve[v]].rev].cap += d
                v = prevv[v]
        return res


while True:
    N = int(input())
    if not N:
        break
    V = 366
    mcf = MinCostFlow(V)
    for i in range(V - 1):
        mcf.add_edge(i, i + 1, 2, 0)
    for _ in range(N):
        s, t, c = map(int, input().split())
        mcf.add_edge(s - 1, t, 1, -c)
    print(-mcf.run(0, V - 1, 2, 10 ** 9))

Submission status: Accepted

Solution code:
while 1:
    N = int(input())
    if N == 0:
        break
    P = [list(map(int, input().split())) for i in range(N)]
    M = 366
    E = [[] for i in range(M)]
    dp = [[0]*(M+1) for i in range(M+1)]
    for t, (i, j, w) in enumerate(P):
        E[i-1].append((t, j, w))
    for i in range(M):
        Ei = E[i]
        for j in range(i, M):
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
        for j in range(M-1, i, -1):
            v = dp[i+1][j+1]
            for _, k, w in Ei:
                if k < j:
                    dp[k+1][j+1] = max(dp[k+1][j+1], v + w)
                else:
                    dp[j+1][k+1] = max(dp[j+1][k+1], v + w)
        v = dp[i+1][i+1]
        for t1, k1, w1 in Ei:
            dp[i+1][k1+1] = max(dp[i+1][k1+1], v + w1)
            for t2, k2, w2 in Ei:
                if t1 <= t2:
                    break
                if k1 < k2:
                    dp[k1+1][k2+1] = max(dp[k1+1][k2+1], v + w1 + w2)
                else:
                    dp[k2+1][k1+1] = max(dp[k2+1][k1+1], v + w1 + w2)
    print(max(max(dpi) for dpi in dp))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Edge():
    def __init__(self,t,f,r,ca,co):
        self.to = t
        self.fron = f
        self.rev = r
        self.cap = ca
        self.cost = co

class MinCostFlow():
    size = 0
    graph = []

    def __init__(self, s):
        self.size = s
        self.graph = [[] for _ in range(s)]

    def add_edge(self, f, t, ca, co):
        self.graph[f].append(Edge(t, f, len(self.graph[t]), ca, co))
        self.graph[t].append(Edge(f, t, len(self.graph[f])-1, 0, -co))

    def min_path(self, s, t):
        dist = [inf] * self.size
        route = [None] * self.size
        que = collections.deque()
        inq = [False] * self.size
        dist[s] = 0
        que.append(s)
        inq[s] = True
        while que:
            u = que.popleft()
            inq[u] = False
            for e in self.graph[u]:
                if e.cap == 0:
                    continue
                v = e.to
                if dist[v] > dist[u] + e.cost:
                    dist[v] = dist[u] + e.cost
                    route[v] = e
                    if not inq[v]:
                        que.append(v)
                        inq[v] = True

        if dist[t] == inf:
            return inf

        flow = inf
        v = t
        while v != s:
            e = route[v]
            if flow > e.cap:
                flow = e.cap
            v = e.fron

        c = 0
        v = t
        while v != s:
            e = route[v]
            e.cap -= flow
            self.graph[e.to][e.rev].cap += flow
            c += e.cost * flow
            v = e.fron

        return dist[t]

    def calc_min_cost_flow(self, s, t, flow):
        total_cost = 0
        for i in range(flow):
            c = self.min_path(s, t)
            if c == inf:
                return c
            total_cost += c

        return total_cost

def main():
    rr = []

    def f(n):
        a = sorted([LI() for _ in range(n)], key=lambda x: [x[1], x[0], -x[2]])
        mcf = MinCostFlow(368)
        s = 366
        t = 367
        for i in range(1,366):
            mcf.add_edge(i-1,i,2,0)
        for i,j,w in a:
            mcf.add_edge(i-1,j,1,-w)
        mcf.add_edge(s,0,2,0)
        mcf.add_edge(365,t,2,0)

        res = mcf.calc_min_cost_flow(s, t, 2)
        return -res

    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))


print(main())