[백준] 1506 경찰서

문제

종욱이가 살고있는 나라에는 도시가 N개 있고, 도시의 일부는 일방 통행 도로로 연결되어 있다. 종욱이가 살고있는 나라의 대통령 욱종이는 범죄와 싸우기 위해서 일부 도시에 경찰서를 세우려고 한다. 도시 i에 경찰서를 세우는 비용은 cost[i] 이다.

도시 i에 세운 경찰서가 도시 j를 통제할 수 있으려면, i에서 j로 갔다가, 다시 돌아오는 경로가 존재해야 한다.

도로가 연결되어 있는 상태와 각 도시에 경찰서를 지을 때 필요한 비용이 주어졌을 때, 모든 도시를 통제하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 각 도시에 경찰서를 세우는데 드는 비용이 주어진다. 셋째 줄부터 도로가 연결되어 있는 상태가 한 줄에 한 줄에 하나씩 주어진다. i번째 줄의 j번째 문자가 0인 경우에는 도시 i에서 도시 j로 갈 수 없는 것이고, 1인 경우에는 갈 수 있는 것이다.

경찰서를 세우는 비용은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 도시를 통제하는데 필요한 최소 비용을 출력한다.

 

도시 a,b가 있을때 a에서b로, b에서a로 갈 수있다면 a와b는 한 사이클 내에 존재합니다.

모든 도시를 최소 비용으로 통제하려면 한 사이클 ㅐ에서는 가장 비용이 낮은 도시만 통제하면 됩니다.

강결합 컴포넌트 문제입니다.

타잔알고리즘으로 scc별로 묶어서,

한 scc 내에서 가장 비용만 더하면 됩니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
int N, cost[101], edge[101][101]; char c;
int v[101], s[101], cnt, num;
vi st;
vvi scc;
int dfs(int k) {
	st.push_back(k);
	int parent = v[k] = ++cnt;
	rep(i, N) {
		if (edge[k][i]) {
			if (!v[i]) {
				parent = min(parent, dfs(i));
			}
			else if (!s[i]) {
				parent = min(parent, v[i]);
			}
		}
	}
	if (parent == v[k]) {
		vi temp;
		num++;
		while (1) {
			auto top = st.back();
			st.pop_back();
			s[top] = num;
			temp.push_back(cost[top]);
			if (top == k)break;
		}
		scc.push_back(temp);
	}
	return parent;
}
int tarjan() {
	rep(i, N) {
		if(!v[i])
			dfs(i);
	}
	return 1;
}
int main() {
	FAST;
	cin >> N;
	rep(i, N)cin >> cost[i];
	rep(i, N)rep(j, N) {
		cin >> c;
		edge[i][j] = c - '0';
	}

	tarjan();
	int sum = 0;
	for (auto r : scc) {
		sum += *min_element(r.begin(), r.end());
	}
	cout << sum;
}