Problem:


問題 F : Social Monsters

問題文

  不思議な生き物と人間が互いに助け合って生きている世界．
  この世界では自分で捕まえたモンスター同士を戦わせる大会が盛んに行われており，
  多くの少年少女達が世界一のトレーナーを目指している．

  バトルでは自分が捕まえたモンスターからパーティを作り，パーティ同士の対戦となる．
  モンスターのペアには相性があり，相性が非常に悪い場合と普通の場合がある．
  相性が非常に悪い場合，そのペアのモンスターを同じパーティに入れることはできない．
  相性が普通の場合には，友情度という数値で相性の良さが表現される．
  バトルでは，パーティ全体の友情度の和が勝負の鍵となる．

  いまN匹のモンスターからK匹のモンスターからなるパーティを作りたい．
  M個のモンスターのペア(a_i, &thinsp; b_i)に対して相性が分かっており，整数 c_i で表されている．
  c_i = 0 のとき，a_i 番目のモンスターと b_i 番目のモンスターは相性が非常に悪いことを意味する．
  c_i &thinsp;&ne;&thinsp; 0 のとき，a_i 番目のモンスターと b_i 番目のモンスターは相性が普通であり，その友情度は c_i であることを意味する．
  与えられたM個のペア以外は，相性が普通であり，それらの友情度はすべて0である．

  パーティの友情度の和を最大にする選び方を考えてみよう．

入力形式

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

N M K
a_0 b_0 c_0
...
a_{M-1} b_{M-1} c_{M-1}

出力形式

K匹のモンスターからなるパーティを作ることができない場合は1行に "Impossible" を出力せよ． 

パーティを作ることができるとき，友情度の和の最大値を出力せよ．

制約

1 ≤ K ≤ N ≤ 2000

0 ≤ M ≤ N 

1 &thinsp; ≤ &thinsp; a_i &thinsp; &ne; &thinsp; b_i &thinsp; ≤ N

|c_i| &thinsp; ≤ 10000

 各モンスターは a_0, a_1, …, a_{M-1}, b_0, b_1, …, b_{M-1} の中に高々2回しか現れない．

 
i &thinsp; &ne; &thinsp; j &ensp; &rArr; &ensp;
\{a_i,&thinsp;b_i\} &thinsp; &ne; &thinsp; \{a_j, &thinsp; b_j\}

入出力例

入力例 1

6 5 4
2 1 1
2 5 2
5 1 1
4 3 2
3 6 -1

出力例 1

4

入力例 2

3 1 3
1 2 -10

出力例 2

-10

入力例 2

6 3 5
1 2 0
2 3 10
3 4 0

出力例 2

Impossible



Sample input:
6 5 4
2 1 1
2 5 2
5 1 1
4 3 2
3 6 -1


Sample output:
4

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N, M, K = map(int, readline().split())
    G = [[] for i in range(N)]
    INF = 10**18
    for i in range(M):
        a, b, c = map(int, readline().split())
        if c == 0:
            c = -INF
        G[a-1].append((b-1, c))
        G[b-1].append((a-1, c))
    def calc(K, U, l):
        if not l:
            X = [-INF]*(K+1)
            S0 = [-INF]*(K+1)
            S1 = [-INF]*(K+1)
            S0[0] = S1[1] = 0
            for i in range(1, K):
                e = U[i]
                for j in range(K-1, -1, -1):
                    S1[j+1] = max(S0[j], S1[j] + e)
                    S0[j] = max(S0[j], S1[j])
            for i in range(K+1):
                X[i] = max(S0[i], S1[i])
        else:
            X = calc(K-1, U[1:], 0) + [-INF]
            S0 = [-INF]*K
            S1 = [-INF]*K
            S0[0] = 0; S1[1] = U[1]
            for i in range(2, K):
                e = U[i]
                for j in range(K-2, -1, -1):
                    S1[j+1] = max(S0[j], S1[j] + e)
                    S0[j] = max(S0[j], S1[j])
            e = U[0]
            for i in range(K):
                X[i+1] = max(X[i+1], S0[i], S1[i] + e)
        return X
    used = [0]*N
    sg = 0
    dp = [-INF]*(N+1)
    dp[0] = 0
    for i in range(N):
        if used[i]:
            continue
        if len(G[i]) == 0:
            used[i] = 1
            for i in range(N-1, -1, -1):
                dp[i+1] = max(dp[i+1], dp[i])
            continue
        if len(G[i]) == 1:
            used[i] = 2
            v, c = G[i][0]
            r = [i]
            u = [0, c]
            while len(G[v]) == 2:
                r.append(v)
                used[v] = 2
                w1, w2 = G[v]
                if used[w1[0]]:
                    v, c = w2
                    u.append(c)
                else:
                    v, c = w1
                    u.append(c)
            r.append(v)
            used[v] = 2
            L = len(r)
            s = calc(L, u, 0)
            for i in range(N-L, -1, -1):
                for j in range(1, L+1):
                    dp[i+j] = max(dp[i+j], dp[i] + s[j])
    for i in range(N):
        if used[i]:
            continue
        r = []
        u = []
        v = i
        while 1:
            r.append(v)
            used[v] = 3
            w1, w2 = G[v]
            if used[w1[0]] and used[w2[0]]:
                break
            if used[w1[0]]:
                v, c = w2
                u.append(c)
            else:
                v, c = w1
                u.append(c)
        if G[i][0][0] == r[-1]:
            c = G[i][0][1]
        else:
            c = G[i][1][1]
        u = [c] + u
        L = len(r)
        s = calc(L, u, 1)
        for i in range(N-L, -1, -1):
            for j in range(1, L+1):
                dp[i+j] = max(dp[i+j], dp[i] + s[j])
    if dp[K] < -10**9:
        write("Impossible\n")
    else:
        write("%d\n" % dp[K])
solve()