#include #include #include #include #include using namespace std; const int NMAX = 13; bool visited[NMAX]; int N; int population[NMAX]; // 인구 int totPopulation; // 총 인구 int aPopulation; vector> v(NMAX); const int defMinDiff = 10000005; int minDiff = defMinDiff; int bCount; int goB(int start,int bPop, int bCnt) { ++bCnt; int p = bPop + population[start]; int m = p; for (int next : v[start]) { if (visited[next] == false) { visited[next] = true; m = goB(next, m, bCnt); visited[next] = false; } } if (m == (totPopulation - aPopulation)) { int diff = abs(aPopulation - m); minDiff = min(diff, minDiff); } return m; } //void goA(int start, int aPop) void goA(int start) { aPopulation += population[start]; for (int i = 1; i <= N; i++) { if (visited[i] == false) { //aPopulation = aPop; visited[i] = true; goB(i, 0, 0); visited[i] = false; break; } } for (int next : v[start]) { if (visited[next] == false) { visited[next] = true; goA(next); visited[next] = false; } } aPopulation -= population[start]; } int main() { ios::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr); cin >> N; for (int i = 1; i <= N; i++) { int temp; cin >> temp; population[i] = temp; totPopulation += temp; } for (int i = 1; i <= N; i++) { int num; cin >> num; for (int j = 0; j < num; j++) { int temp; cin >> temp; v[i].push_back(temp); } } bCount = N; for (int i = 1; i <= N; i++) { visited[i] = true; //goA(i, 0); goA(i); visited[i] = false; } if (defMinDiff == minDiff) { cout << "-1\n"; } else cout << minDiff << "\n"; }

제출 #108954

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: