문제
https://www.acmicpc.net/problem/1506
문제해설
모든 도시를 경찰서의 통제하에 두려고 한다.
도시끼리 이동할 수 있다면 한 군데에만 경찰서를 세우면 된다.
경찰서를 짓는 비용은 도시마다 다르며
조건을 만족하여 모든 도시를 경찰의 통제하에 두는 최소 비용을 구하면 된다.
문제풀이
SCC를 이용하여 한 SCC에 속해있는 도시 중
경찰서 건설 비용이 가장 낮은 도시들을 선택하면 된다.
그렇게 모든 SCC들의 비용을 다 더하면 정답이다.
전체코드
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
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<limits.h>
using namespace std;
typedef long long ll;
vector<vector<int>>arr;
int cost[101], discover[101], scc[101], cnt;
stack<int>st;
ll res;
int dfs(int now) {
st.push(now);
discover[now] = cnt++;
int parent = discover[now];
for (int i = 0; i < arr[now].size(); i++) {
int next = arr[now][i];
if (discover[next] == -1)
parent = min(parent, dfs(next));
else if (scc[next] == -1)
parent = min(parent, discover[next]);
}
if (parent == discover[now]) {
int tmp = INT_MAX;
while (true) {
int here = st.top();
st.pop();
scc[here] = 1;
tmp = min(tmp, cost[here]);
if (here == now)
break;
}
res += tmp;
}
return parent;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
arr.resize(n + 1);
for (int i = 1; i <= n; i++) {
int c; cin >> c;
cost[i] = c;
}
for (int i = 1; i <= n; i++) {
string s; cin >> s;
for (int j = 0; j < n; j++) {
if (s[j] == '1')
arr[i].push_back(j + 1);
}
}
fill(discover, discover + 101, -1);
fill(scc, scc + 101, -1);
for (int i = 1; i <= n; i++) {
if (discover[i] == -1)
dfs(i);
}
cout << res;
return 0;
}