https://www.acmicpc.net/problem/1506


좀 도와주십셔 형님들


그냥 아주 일반적인 scc 문제라고 생각되고, scc로 나눈 다음 각 ssc 내에서 제일 cost작은 놈 찾아서 그거 다 합하면 되는 문제 아닌가여?




#include <bits/stdc++.h>
using namespace std;
vector<int> rel[100];
vector<int> rel_re[100];
int vst[100];
deque<int> topo;
void dfs(int cur) {
vst[cur] = true;
for(int nxt:rel[cur]) {
if (vst[nxt]) {
continue;
}
dfs(nxt);
}
topo.push_front(cur);
}
void dfs2(vector<int>& scc, int cur) {
vst[cur] = true;
scc.push_back(cur);
for(int nxt:rel_re[cur]) {
if (vst[nxt]) {
continue;
}
dfs2(scc,nxt);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
int cost[101];
cin >> n;
for(int i=0;i<n;i++) {
cin >> cost[i];
}
for(int i=0;i<n;i++) {
string s;
cin >> s;
for(int j=0; j<n ; j++ ) {
if (s[j] == '1') {
rel[i].push_back(j);
rel_re[j].push_back(i);
}
}
}
for(int i=0;i<n;i++) vst[i] = false;
for(int i=0;i<n;i++) {
if (vst[i]) continue;
dfs(i);
}
// for(auto i:topo) cout << i << ' ';
// cout << ' ';
// for(int i=0;i<n;i++) {
// cout << i << " : ";
// for(auto nxt:rel[i]) cout << nxt << ' ';
// cout << ' ';
// }
for(int i=0;i<n;i++) vst[i] = false;
vector<vector<int>> sccs;
for(int i=0;i<n;i++) {
if (vst[i]) continue;
vector<int> scc;
dfs2(scc,i);
sccs.push_back(scc);
}
int answer = 0;
int cnt = sccs.size();
for(int i=0;i<cnt;i++) {
int temp = 2147483647;
for(int inside:sccs[i]) {
temp = min(temp,cost[inside]);
}
answer += temp;
}
cout << answer;
}




책에서 배운대로 먼저 scc로 분해하기 위해서 먼저 dfs를 돌려고 끝난 순서대로 topo 라는 deque 에다가 push_front로 넣었고

그 후 vst 초기화 시켜주고


topo 순서대로 다시 dfs돌릴 때 반대로된 rel로 돌려서 scc 분리해냈음. sccs라는 거에다가 각각의 scc(백터)를 모아줬구여


거의 동일한 dfs인데 처음 돌릴 때랑 나중에 돌릴 때를 따로 만들어둔 건 내가 봐도 세련되지 못한 것 같긴 한데 그건 그거고


로직상 틀린 점은 없어 보이고 샘플 데이터들도 다 scc 잘 나누고 그 뒤로 각 scc 내에서 제일 cost 싼 것들 잘 뽑아오는 걸로 보이는데


5%에서 계속 틀리네요


뭐가 문제일까요