Untitled
unknown
python
6 months ago
3.7 kB
0
Indexable
Never
from sys import stdin from itertools import combinations as combi input = stdin.readline N = int(input()) populations = list(map(int,input().split())) all = sum(populations) graph = [set() for _ in range(N)] for idx in range(N): size, *nums_list = map(int,input().split()) for i in range(size): nums_list[i]-=1 graph[idx].add(nums_list[i]) for index in nums_list: graph[index].add(idx) target = [i for i in range(N)] target_set = set(target) from collections import deque as deq ret = 100000 def bfs(possible): global ret, all, N flag1 = False flag2 = False first = deq() first.append(possible[0]) # possible1 | possible2 vis = [True for _ in range(N)] for idx in possible: vis[idx] = False vis[possible[0]] = True possible1 = deq() # print(vis,possible) for idx in range(N): if(vis[idx]): possible1.append(idx) second = deq() second.append(possible1[0]) while(first): cur = first.popleft() for idx in graph[cur]: # print(vis,len(possible), graph[0], possible[0]) if(not vis[idx]): # False만 지나다닐 수 있음. vis[idx] = True first.append(idx) cnt1 = 0 for i in possible: if(vis[i]): cnt1+=1 if(cnt1==len(possible)): # print(cnt1, len(possible)) flag1 = True # exit(0) else: return # 통과 second = deq() vis1 = [False for i in range(N)] for i in possible: vis1[i] = True for i in range(N): if(not vis1[i]): second.append(i) break while second: cur_second = second.popleft() for idx in graph[cur_second]: if(not vis1[idx]): vis1[idx] = True second.append(idx) cnt2 = 0 for i in possible: vis1[i] = False cnt2 = vis1.count(True) if(cnt2 == N - cnt1): flag2 = True if(flag1 and flag2): tmp_sum_1 = 0 for idx in possible: tmp_sum_1 += populations[idx] tmp_sum_2 = all - tmp_sum_1 # all >= tmp_sum1 ret = min(ret, abs(tmp_sum_1-tmp_sum_2)) return else: return def bfs2(possible): global N, ret flag = False vis = [True for _ in range(N)] for idx in possible: vis[idx] = False first = deq() first.append(possible[0]) vis[possible[0]] = True C = 1 while first: cur = first.popleft() for new_idx in graph[cur]: if(not vis[new_idx]): C+=1 vis[new_idx] = True if(C==len(possible)): tmp = 0 for idx in possible: tmp += populations[idx] ret = min(tmp,ret) # print(ret,"!331") return else: return blank = False idx = 0 cnt = 0 for i in range(N): if len(graph[i])==0: idx = i blank = True cnt+=1 # break if(not blank): for i in range(1,N): # print(i) for possible in combi(target,i): bfs(possible) else: if(cnt==1): # find_min value if(N==2): ret = abs(populations[0]-populations[1]) print(ret,3131) else: new_target_set = target_set - {idx} end = False for possible in combi(new_target_set,N-1): bfs2(possible) if(ret==100000): pass else: ret = abs(ret-populations[idx]) elif cnt==2: ret = abs(populations[0]-populations[1]) if(ret==100000): print(-1) else: print(ret)