Vertex Merge Game

• 함정이 좀 있는 문제이다.
• 우선, 웅배가 얻을수 있는 점수의 상한은 maximum spanning tree 에 해당하는 엣지들만 선택했을 경우에 얻는 점수이다.
• 그리고 유니가 어떤 식으로 red/blue를 나누든 웅배는 항상 maximum spanning tree에 포함되는 엣지들을 고를수가 있다 (이부분 엄밀한 증명은 생략). 그말은, 웅배는 유니의 행동에 관계 없이 항상 점수의 상한값을 얻을 수 있다는 뜻이다.
• 그러면 유니의 행동에 관계 없이 웅배가 얻는 점수가 동일하다면, 유니도 웅배의 행동은 신경쓰지 말고 자기가 가장 높은 점수를 얻을 수 있는 행동을 해야 한다. 그것은 항상 red와 blue를 전체 갯수의 반반으로 나누는 것이다.
• 결국 유니와 웅배 모두 상대는 신경쓰지 말고 자신이 얻을수 있는 최대 점수를 얻도록 행동하게 되고, 이때 유니와 웅배가 얻는 점수를 비교해서 답을 출력하면 끝이다.
• maximum spanning tree를 구하기 위해서 O(ElogE)가 걸리고, 유니의 점수를 계산하기 위해서는 O(V)가 걸린다. E>V 이므로 전체 시간복잡도는 O(ElogE)

"""Solution code for "BOJ 23736. Vertex Merge Game".

- Problem link: https://www.acmicpc.net/problem/23736
- Solution link: http://www.teferi.net/ps/problems/boj/23736

Tags: [game theory]
"""

import sys
from teflib import graph as tgraph


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    edges = []
    for _ in range(M):
        u, v, w = [int(x) for x in sys.stdin.readline().split()]
        edges.append((u - 1, v - 1, -w))

    mst_edges = tgraph.minimum_spanning_tree(edges, N)
    woongbae = -sum(w for _, _, w in mst_edges)
    yunee = sum((i // 2) * ((i + 1) // 2) for i in range(N + 1))
    if yunee == woongbae:
        print('tie')
    else:
        print('win' if yunee > woongbae else 'lose')


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.minimum_spanning_tree