PS와 개발을 공부하자

2017 카카오 코드페스티벌) F. 신비로운 유적 탐험 본문

Algorithm/Problem Solving

2017 카카오 코드페스티벌) F. 신비로운 유적 탐험

sgc109 2017.08.19 21:51

문제 링크


노드의 수가 100개 이하인 두개의 트리 g1, g2 가 주어진다. 두 트리의 루트 노드는 모두 1번 노드이다.

두 트리의 최대 공통 노드 수를 출력하는 문제이다. 쉽게 말해서 각 노드에 대해서

자식 노드들의 순서를 요리 조리 바꿔도 여전히 같은 트리이기 때문에 각 노드의 자식들의 순서를

요리 조리 바꿨을 때 두 트리중 모양이 일치하는 가장 노드가 많은 부분 트리의 노드 수를 구하는 문제이다.


dp[a][b] : 트리 g1에서 노드 a를 루트로 하는 서브트리와, 트리 g2에서 노드 b를 루트로 하는 서브트리의

최대 공통 노드 수

라고 부분 문제를 정의하면 트리 dp 로 해결할 수가 있다.

그렇다면 부분 문제 테이블의 하나의 셀을 어떻게 채울까? 

답은 MCMF 이다.

dp[a][b] 에서 a의 자식들을 왼쪽부터 순서대로 ac1, ac2, ...  이고, 

b의 자식들을 왼쪽부터 bc1, bc2, ... 라고 해보자. 그렇다면 유량 그래프를 구성할 수가 있고 비용은

전에 구해놓은 부분 문제들의 값을 이용하면된다.

물론 용량은 모두 1이며 소스 또는 싱크와 연결된 간선들에서의 비용은 물론 0이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <cstring>
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
 
using namespace std;
const int inf = 0x3c3c3c3c;
 
struct MCMF {
    struct edge {
        int to, cap, cost, rev;
    };
    int size, src, sink;
    vector<vector<edge> > G;
    vector<int> dist, par, edgeIdx;
    MCMF(int sizeint src, int sink) {
        G = vector<vector<edge> >(size);
        par = vector<int>(size);
        edgeIdx = vector<int>(size);
        this->size = size;
        this->src = src;
        this->sink = sink;
    }
    bool spfa() {
        vector<bool> inQ = vector<bool>(sizefalse);
        queue<int> q;
        q.push(src);
        inQ[src] = true;
        dist[src] = 0;
        while (!q.empty()) {
            int here = q.front();
            q.pop();
            inQ[here] = false;
            for (int i = 0; i < (int)G[here].size(); i++) {
                auto e = G[here][i];
                if (e.cap > 0 && dist[here] + e.cost < dist[e.to]) {
                    dist[e.to] = dist[here] + e.cost;
                    par[e.to] = here;
                    edgeIdx[e.to] = i;
                    if (!inQ[e.to]) q.push(e.to), inQ[e.to] = true;
                }
            }
        }
        if (dist[sink] >= 0return false;
        return dist[sink] != inf;
    }
    pair<intint> getMCMF() {
        int maxFlow = 0;
        int minCost = 0;
        while (1) {
            dist = vector<int>(size, inf);
            if (!spfa()) break;
            int minFlow = inf;
            int costSum = 0;
            for (int p = sink; p != src; p = par[p]) {
                auto& e = G[par[p]][edgeIdx[p]];
                minFlow = min(minFlow, e.cap);
                costSum += e.cost;
            }
            for (int p = sink; p != src; p = par[p]) {
                auto& e = G[par[p]][edgeIdx[p]];
                e.cap -= minFlow;
                G[e.to][e.rev].cap += minFlow;
            }
            maxFlow += minFlow;
            minCost += costSum * minFlow;
        }
        return { maxFlow, minCost };
    }
    void addEdge(int from, int to, int cap, int cost) {
        G[from].push_back({ to, cap, cost, (int)G[to].size() });
        G[to].push_back({ from, 0-cost, (int)G[from].size() - 1 });
    }
};
vector<int> G1[103], G2[103];
int dp[103][103];
 
int go(int cur1, int dad1, int cur2, int dad2) {
    int& cache = dp[cur1][cur2];
    if (cache != -1return cache;
    int N1 = G1[cur1].size();
    int N2 = G2[cur2].size();
    int src = N1 + N2, sink = src + 1;
    MCMF mcmf(2 + N1 + N2, src, sink);
    for (int i = 0; i < N1; i++) {
        int u = G1[cur1][i];
        if (u == dad1) continue;
        for (int j = 0; j < N2; j++) {
            int v = G2[cur2][j];
            if (v == dad2) continue;
            int cost = go(u, cur1, v, cur2);
            mcmf.addEdge(i, N1 + j, 1-cost);
        }
        mcmf.addEdge(src, i, 10);
    }
    for(int i = 0 ; i < N2; i++){
        int u = G2[cur2][i];
        mcmf.addEdge(N1 + i, sink, 10);
    }
    int ret = -mcmf.getMCMF().second + 1;
    return cache = ret;
}
int solution(int n1, vector<vector<int>> g1, int n2, vector<vector<int>> g2) {
    memset(dp, -1sizeof(dp));
    for (int i = 0; i < 103; i++) G1[i].clear(), G2[i].clear();
    for (auto v : g1) {
        int a = v[0], b = v[1];
        G1[a].push_back(b);
        G1[b].push_back(a);
    }
    for (auto v : g2) {
        int a = v[0], b = v[1];
        G2[a].push_back(b);
        G2[b].push_back(a);
    }
    return go(1010);
}
 
cs



0 Comments
댓글쓰기 폼