Learning Algorithms

アルゴリズムの勉強メモ

CS Academy 060 E. Flip the Edges

CS Academy 060 E. Flip the Edges

CS Academy

感想

DPの書き方がよくわからなかったので、pekempeyさんより解説をいただきました。

解法

まず二度以上選ぶ辺は存在しないことが言えます。なぜなら、もし仮にそのような部分があるとき、そのような部分は反転しなかったことにすれば、パスの個数は同じまま辺の数を減らせるからです。

まずパスの数を最小化し、それが同じなら辺の数を最小化する、ということなので、(パスの数, 辺の数)というペアで状態を持ってDPができればよいとわかります。これをどのように持ってどのように遷移するかが問題です。

$dp_0$ を根からの辺がもう余っていない部分木、$dp_1$ を根からの辺が一本余っていて、これからどこかに繋ぐことができる状態の部分木(その辺はまだ使ったものとはカウントしない)、と定義すると、次の遷移を考えることができます。ただし辺が二本以上余るような状態は無駄なので、考慮しなくて良いです。

f:id:KokiYamaguchi:20171209111446j:plain

これは、一本のパスというのは両端で完結している(それはそうなのですが)という性質を陽に持つことで、無駄なく使っているパスの個数を漏れなく数えるということをきれいにやっています。

この遷移をそのまま書けば、答えは $dp_0 $です。

実装
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

#define mp make_pair

static const int INF = 0x3f3f3f3f;

struct edge {
        int to;
        int type; //0 -> choose, 1 -> not choose, 2 -> whichever
};

int main() {
        int n;
        scanf("%d", &n);
        vector<vector<edge>> g(n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b, c, d;
                scanf("%d%d%d%d", &a, &b, &c, &d);
                a --, b --;
                if (d != 2) d = c != d;
                g[a].push_back({b, d});
                g[b].push_back({a, d});
        }
        vector<pair<int, int>> dp0(n), dp1(n);
        function<void (int, int)> dfs = [&](int u, int prev) {
                dp0[u] = mp(0, 0);
                dp1[u] = mp(1, 0);
                for (auto e : g[u]) { 
                        int v = e.to, type = e.type;
                        if (v == prev) continue;
                        dfs(v, u);
                        pair<int, int> x0(dp0[u].first + dp0[v].first, dp0[u].second + dp0[v].second);
                        pair<int, int> y0(dp1[u].first + dp0[v].first, dp1[u].second + dp0[v].second);
                        pair<int, int> x1(dp1[u].first + dp1[v].first - 1, dp1[u].second + dp1[v].second + 1);
                        pair<int, int> y1(dp0[u].first + dp1[v].first, dp0[u].second + dp1[v].second + 1);
                        if (type == 0) {
                                dp0[u] = x0;
                                dp1[u] = y0;
                        } else if (type == 1) {
                                dp0[u] = x1;
                                dp1[u] = y1;
                        } else {
                                dp0[u] = min(x0, x1);
                                dp1[u] = min(y0, y1);
                        }
                }
        };
        dfs(0, -1);
        printf("%d %d\n", dp0[0].first, dp0[0].second);
        return 0;
}