[白俊]17471号ゲリーマンデリン

				  [점심먹고 아아 수혈하는 짤]

https://www.acmicpc.net/problem/17471
最近会社のことで、アルゴリズムの問題を全然考えていません.
しかし、たゆまぬ努力が実力を高めるので、週末に問題を作ります!
問題の説明
問題は、すべての要素を接続する一方向図を2つのすべての要素を接続する一方向図に分けることです.
各ノードには1つの値があり、2つのグラフィックの値の和の差は最小の値を返します.
方法

グラフのノード数は最大で10なので、暴力的に解くべきだと思います.

パターンをA、Bに分けると、暴力的に分ける方法は次のとおりです.

A 1ノードB 2~10ノード、

A 2ノードBは、1、3~10ノード、

である.

Aは、3ノードBが1,2,4~10ノードを表す.
....

Aは1ノード、2ノードBは3〜10ノードである.
...
このように分けることができます.

このように分けると
10C1+10C2+10C3.. + 10 Cには10の候補があり、nC 1+nC 2...ncn=2^n(n=10).
2^nは2^10=1024であり,各候補呼び出しDFSの時間的複雑度はO(v+e)であるため,最大10 C 2である.したがって,総演算量の上限は2^10 x 10 C 2であり,Brootforceで完全に解くことができる!
アルゴリズム#アルゴリズム#

の組み合わせでグラフを2つに分けます.

で分割された2つのノードについて、dfsを回転させて、接続されたグラフィックであるかどうかを決定する.

2の条件が真である場合、2つの要素の合意差が格納される.

コード#コード#

from itertools import combinations

MAX = (10000000000000000000)
if __name__ == "__main__":
    n = int(input())
    answer=MAX
    populations = list(map(int,input().split()))
    populations.insert(0,0)
    graph = [ 0 for _ in range(n+1)]
    for i in range(1,n+1):
        temp = list(map(int,input().split()))[1:]
        graph[i]=temp
    allNodes=set(range(1,n+1))
    
    def isConnected(nodes:tuple) -> bool:
        visited = [False for _ in range(n+1)]
        def DFS(node):
            visited[node] = True
            for nextNode in graph[node]:
                if nextNode in nodes and not visited[nextNode]:
                    DFS(nextNode)
        DFS(nodes[0])
        for i in nodes:
            if not visited[i]: return False
        return True
    
    def costCalculator(nodes):
        return sum(populations[i] for i in nodes) 

    for i in range(1,n):
        for combination in combinations(range(1,n+1),i):
            nodesA = tuple(allNodes - set(combination))
            nodesB = combination
            if isConnected(nodesA) and isConnected(nodesB):
               answer=min(abs(costCalculator(nodesA)-costCalculator(nodesB)),answer)
    print(answer if answer != MAX else -1)