# Untitled

unknown
python
5 months ago
3.8 kB
2
Indexable
Never
```from sys import stdin
from itertools import combinations as combi

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

for index in nums_list:

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)
# for idx, row in enumerate(graph):
#     print(idx, *row)

```