codeforces #148 World Eater Brothers

問題概要

n個の節点がn-1個の有向枝で結ばれている。枝の方向を考えなければこのグラフは連結である。節点集合から2つの節点を選び、その2点を始点とすればすべての節点へ到達できるようにしたい。2つの節点を最適に選んだときに、向きを変更しなければならない枝の数の最小値を求めよ。

方針

節点集合をVとして、Vを2つの集合に分ける。これをU, Wとする。 Uから最適な節点を選び、その節点からU内のすべての節点へ到達できるようにした場合にかかるコスト（変更すべき枝の向き）を計算する。Wも同様のことをする。
すべてのV -> {U, W}分割について上記を行い、（Uにかかるコスト + Wにかかるコスト）の最小値を求めればよい。
問題のグラフは辺の方向を考えなければ木なので、V -> {U, W}の分割の方法は枝の数だけある。
U, Wからそれぞれ最適な頂点を選ぶ処理は、O(|U|), O(|W|)なので、全体として、O(n²)で計算できる。

ソースコード

int n;
vector<pair<int, int> > G[3000];

int dfs(int v, int p) {
    int ret = 0;

    REP (i, G[v].size()) {
        int u = G[v][i].first;
        int dir = G[v][i].second;

        if (u == p)
            continue;

        ret += dfs(u, v) + (dir == -1);
    }
    return ret;
}

int chRoot(int v, int p, int acc) {
    int ret = acc;
    
    REP (i, G[v].size()) {
        int u = G[v][i].first;
        int dir = G[v][i].second;

        if (u == p)
            continue;
        
        ret = min(ret, chRoot(u, v, acc + dir));
    }

    return ret;
}

int solve() {
    if (n < 3)
        return 0;

    int ret = 1<<30;
    REP (v, n) REP(i, G[v].size()) {
        int u = G[v][i].first;
        int acc1 = dfs(v, u);
        int acc2 = dfs(u, v);
        
        ret = min(ret, chRoot(v, u, acc1) + chRoot(u, v, acc2));
    }
    return ret;
}

int main() {
    cin >> n;
    REP (i, n-1) {
        int a, b;
        cin >> a >> b;
        G[--a].push_back(make_pair(--b, 1));
        G[b].push_back(make_pair(a, -1));
    }

    cout << solve() << endl;

    return 0;
}