[白俊]17471号ゲリーマンデリン
[점심먹고 아아 수혈하는 짤]最近会社のことで、アルゴリズムの問題を全然考えていません.
しかし、たゆまぬ努力が実力を高めるので、週末に問題を作ります!
問題の説明
問題は、すべての要素を接続する一方向図を2つのすべての要素を接続する一方向図に分けることです.
各ノードには1つの値があり、2つのグラフィックの値の和の差は最小の値を返します.
方法
....
...
このように分けることができます.
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で完全に解くことができる!
アルゴリズム#アルゴリズム#
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)Reference
この問題について([白俊]17471号ゲリーマンデリン), 我々は、より多くの情報をここで見つけました https://velog.io/@ha-mulan/백준-17471번-게리맨더링テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol