11097 도시계획

11097 도시 계획 https://www.acmicpc.net/problem/11097

리스트가 하나 주어진다.
이 리스트는 $i$에서 $j$로 갈 수 있는 경로가 존재한다면 1, 절대 못간다면 0으로 나타냈다.
우리는 가장 적은 간선을 사용해서 이 리스트처럼 갈 수 있도록 해야한다.
이때 필요한 가장 적은 간선의 갯수와 그 간선을 구하는 문제이다.

주어진 리스트로 일단 SCC를 구해서 SCC내부의 정점들이 $u, v, k, d$라면 
$u$->$v$, $v$->$k$, $k$->$d$, $d$->$u$가 최소 간선을 사용해서 만드는 방법은 쉽게 구할 수 있다.

문제는 서로 다른 SCC간에 최적 간선이다.
주어진 리스트에서 불필요한 간선이 있기 때문에 이 간선들을 삭제시켜야 하는데 
플로이드 와샬 알고리즘을 사용하면 해결할 수 있다.

코드가 너무길어 부분만 올린다.

for (int n = 0;n < N;n++) {             for (int m = 0;m < N;m++) {                 //그래프 압축 후 다른 scc간에 연결 시켜줌                 if (map[n][m] == '0' || n == m || scc[n] == scc[m]) continue;                 adj_scc[scc[n]][scc[m]] = true;               }         }         //연결된것은 최적값이 아님 (scc간에 연결은 간선 1개면 충분)         for (int k = 0;k < scc_cnt;k++) {             for (int n = 0;n < scc_cnt;n++) {                 for (int m = 0;m < scc_cnt;m++) {                     //n->k, k->m으로 간다면 n->m은 삭제 가능                     if (adj_scc[n][m] && adj_scc[n][k] && adj_scc[k][m]) adj_scc[n][m] = 0;                 }             }         }         vector<pair<int, int>> ans;                  // <답 1차 저장> scc내부간에 간선 저장         for (int n = 0;n < scc_cnt;n++) {             int getsize = (int)group_scc[n].size();             if (getsize > 1) {        // scc내부 정점이 여러개라면 u->v->d->k->u 형식으로 묶어줌 (최소)                 for (int m = 0;m < getsize - 1;m++)                     ans.push_back({ group_scc[n][m],group_scc[n][m + 1] });                 ans.push_back({ group_scc[n][getsize - 1],group_scc[n][0] });             }         }         // <답 2차 저장> 서로 다른 scc간에 간선 저장         for (int n = 0;n < scc_cnt;n++) {             for (int m = 0;m < scc_cnt;m++) {                 if (adj_scc[n][m]) {                     //순서에 상관없으므로 첫번째 걸로 저장                     ans.push_back({ group_scc[n][0], group_scc[m][0] });                 }             }         } Colored by Color Scripter

cs

                                                                       <600 돌파 !!!>