백준/[삼성 기출]

[17471번] 게리맨더링

2744m 2020. 4. 11. 20:49
17471번: 게리맨더링
 
www.acmicpc.net

 

1. 각 지역들이 어느 선거구에 포함될지 정한다. (조합)

2. 나눠진 선거구안의 지역들을 bfs하면서 서로 이어져 있으면 union find를 이용해 묶어준다.

3. 각 선거구 지역들이 다 이어졌으면 두 선거구의 인구차를 구해서 최솟값 갱신을 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#define vi vector<int> 
#define vvi vector<vi>
using namespace std;
int N, M;
//vvi connect(11); vvi tmp(11);
vi A, B;
int value[11], arr[11];
int connect[11][11], tmp[11][11];
int _union_[11];
int cnt, ans = 1e9;
 
void set() {
    for (int i = 1; i <= N; i++)
        _union_[i] = i;
}
 
int _find_(int tar) {
    if (tar == _union_[tar]) return tar;
    else return _union_[tar] = _find_(_union_[tar]);
}
 
void uni(int a, int b) {
    a = _find_(a);
    b = _find_(b);
    if (a != b) _union_[b] = a;
}
 
void disconnect(vi team) {
    for (int i = 0; i < team.size(); i++) {
        int j = 0;
        int now = team[i];
        for (int j = 1; j <= N; j++) {
            if (tmp[now][j] == 1 && !binary_search(team.begin(), team.end(), j))
                tmp[now][j] = tmp[j][now] = 0;
        }
    }
}
 
bool chk(vi team) {
    for (int i = 1; i < team.size(); i++) {
        if (_union_[team[0]] != _union_[team[i]]) {
            return false;
        }
    }
    return true;
}
 
void p(int c) {
    for (int i = 0; i < A.size(); i++)
        cout << A[i] << ' ';
    cout << ": A  ";
    for (int i = 0; i < B.size(); i++)
        cout << B[i] << ' ';
    cout << ": B\n";
    cout << c << '\n';
}
 
void bfs(int s) {
    queue<int>Q;
    int visit[11];
    memcpy(visit, arr, sizeof(visit));
    Q.push(s);
    visit[s] = 1;
    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();
        for (int i = 1; i <= N; i++) {
            if (tmp[now][i] == 1 && visit[i] == 0) {
                visit[i] = 1;
                Q.push(i);
                uni(now, i);
            }
        }
    }
 
}
 
void setTeam(int tar, int dep, int idx) {
    if (tar == dep) {
        set();
        for (int i = 1; i <= N; i++)
            if (!binary_search(A.begin(), A.end(), i))
                B.push_back(i);
        memcpy(tmp, connect, sizeof(tmp));
        disconnect(A);
        disconnect(B);
        
        /*for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (tmp[i][j] == 1)
                    uni(i, j);
            }
        }*/
        if (A.size() > 1)bfs(A[0]);
        if (B.size() > 1)bfs(B[0]);
 
        if (chk(A) && chk(B)) {
            int Asum = 0, Bsum = 0;
            for (int i = 0; i < A.size(); i++)
                Asum += value[A[i]];
            for (int i = 0; i < B.size(); i++)
                Bsum += value[B[i]];
            ans = min(abs(Asum - Bsum), ans);
            //p(abs(Asum - Bsum));
        }
    
        B.clear();
        return;
    }
    else {
        for (int i = idx; i <= N; i++) {
            A.push_back(i);
            setTeam(tar, dep + 1, i + 1);
            A.pop_back();
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> value[i];
        _union_[i] = i;
    }
    for (int i = 1; i <= N; i++) {
        cin >> M;
        for (int j = 0; j < M; j++) {
            int in;
            cin >> in;
            connect[i][in] = 1;
        }
    }
 
    for (int i = 1; i <= N/2; i++)
        setTeam(i, 0, 1);
 
    if (ans == 1e9) ans = -1;
    cout << ans;
    return 0;
}
 
cs