백준 1506 경찰서

문제 URL : https://www.acmicpc.net/problem/1506

1506번: 경찰서

 

문제접근법 : 

scc 알고리즘 문제입니다.

 

scc로 묶은후 scc안에 있는 노드들중 가작 cost가 낮은 것을 선택해서

모든 합을 구하면 되는문제입니다. 

소스코드 : 

#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> vscc,adj;
vector<int> cost,check,finish,st;
int id=0;
void input(){
	cin>>n;
	adj =vector<vector<int>>(n+1);
	cost = check = finish = vector<int>(n+1);
	for(int i=1;i<=n;i++)cin>>cost[i];
	char c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>c;
			if(c=='1')
				adj[i].push_back(j);
		}
	}
}
int scc(int cur){
	check[cur]=++id;
	int root = check[cur];
	st.push_back(cur);
	for(int next:adj[cur]){
		if(check[next]==0)root=min(root,scc(next));
		else if(!finish[next])root= min(root,check[next]);
	}
	if(check[cur]==root){
		vector<int> v;
		while(true){
			int node = st.back();
			st.pop_back();
			v.push_back(node);
			finish[node]=1;
			if(cur==node)break;
		}
		vscc.push_back(v);
	}
	return root;
}
void solve(){
	int res = 0;
	for(int i=1;i<=n;i++){
		if(check[i]==0)scc(i);
	}
	for(vector<int>&v :vscc){
		int Min= 1e8;
		for(int i:v){
			Min = min(cost[i],Min);
		}
		res+=Min;
	}
	cout<<res<<"\n";
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	input();
	solve();
}

궁금한점 혹은 모르는점 논리적인 오류등

어떤 질문이든 댓글은 언제나 환영입니다.