코드 복사/붙여넣기 하는 당신이 아름답습니다.

11745: King’s Inspection

풀이

M <= N+20이므로, 주어지는 그래프는 최대 20개의 간선만 제거하면 트리가 된다.

즉, 트리와 아주 유사하게 생겼다는 뜻이고, 이는 대부분 노드의 in/out degree가 1이라는 뜻이다.

indegree 또는 outdegree가 2 이상인 노드를 special node로 두자.

special node에서 다른 speical node까지의 경로를 압축하자.

in/out degree가 1인 노드들을 모두 압축해서 하나의 간선으로 치는 것이다.

그러면 노드가 많아야 40개인 그래프가 나온다.

이 그래프에서 TSP를 하면 된다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, zip_cnt, zip_num[111111];
int in_deg[111111], out_deg[111111];
vector<int> gp1[111111], path;
struct edg {
    int idx; // zipped index
    vector<int> path; // [s, e)
};
vector<edg> gp2[111];

void zip(int now, int root, int is_root) {
    if (!is_root && zip_num[now]) {
        gp2[zip_num[root]].push_back({ zip_num[now],path });
        return;
    }
    path.push_back(now);
    for (int nxt : gp1[now]) zip(nxt, root, 0);
    path.pop_back();
}

int chk[111];
vector<pair<int, int>> dap;
int feasible(int now, int cnt) {
    if (chk[now]) return (cnt == n && now == 1);
    chk[now] = 1;
    for (int i = 0; i < gp2[now].size(); i++) {
        edg nxt = gp2[now][i];
        dap.push_back({ now,i });
        if (feasible(nxt.idx, cnt+nxt.path.size())) {
            return 1;
        }
        dap.pop_back();
    }
    chk[now] = 0;
    return 0;
}

int main() {
    scanf("%d %d", &n, &m);
    while (m--) {
        int u, v; scanf("%d %d", &u, &v);
        gp1[u].push_back(v);
        in_deg[v]++;
        out_deg[u]++;
    }

    for (int i = 1; i <= n; i++) {
        if (in_deg[i] > 1 || out_deg[i] > 1 || i == 1) {
            zip_num[i] = ++zip_cnt;
        }
        if (in_deg[i] < 1 || out_deg[i] < 1) {
            puts("There is no route, Karl!");
            return 0;
        }
    }

    for (int i = 1; i <= n; i++)
        if (zip_num[i]) zip(i, i, 1);

    if (feasible(1, 0)) {
        for (auto i : dap) for (auto j : gp2[i.first][i.second].path)
            printf("%d ", j);
        puts("1");
    }
    else {
        puts("There is no route, Karl!");
    }

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2019-08-30 14:55

Read more posts by this author