Codeforces Round #135 (Div. 2) D : Choosing Capital for Treeland
問題概要
頂点数V(<2e5)の有向グラフがある。無向にしたときは木になっている。どれかを根にして、辺の向きを入れ替えて有向木になるようにしたいが、その際入れ替える本数を最小化したい。最小値と、どの頂点を根にすればよいかを全て求める問題。
解法
適当に根を決め打ちしてDFSなどで各部分有向木について向きが逆になっている辺の個数などを求めておく。
この情報があると、各頂点について根に選んだとき入れ替えなければならない辺の本数を求めることができる。
図の青で囲んだ部分以外については逆向きな辺の本数を数えて、青で囲んだ部分については順向きな辺の本数を数えれば良い。
acceptされたコード
#include <cstdio> #include <vector> using namespace std; struct Edge { int to; bool orig; Edge(){} Edge(int to, bool orig): to(to), orig(orig) {} }; struct Graph : vector< vector<Edge> > { int numV; Graph(){} void init(int numV_) { numV = numV_; init(); } void init() { assign(numV, vector<Edge>()); } void addDirectedEdge(int from, int to) { operator [](from).push_back(Edge(to, true)); operator [](to).push_back(Edge(from, false)); } }; template<typename numType> inline bool updateMin(numType& old, const numType& test) { if (old > test) { old = test; return true; } return false; } int N; Graph G; const int MAX_N = int(2e5); int size[MAX_N], ord[MAX_N], rev[MAX_N], opt[MAX_N], parent[MAX_N], depth[MAX_N]; bool visited[MAX_N]; void init() { scanf("%d", &N); G.init(N); for (int _ = 0; _ < N - 1; ++_) { int from, to; scanf("%d%d", &from, &to); --from; --to; G.addDirectedEdge(from, to); } } void dfs(int v) { visited[v] = true; size[v] = 1; for (int i = 0; i < int(G[v].size()); ++i) { const int u = G[v][i].to; bool order = G[v][i].orig; if (!visited[u]) { parent[u] = v; depth[u] = depth[v] + 1; ord[u] = ord[v] + (order ? 1 : 0); dfs(u); size[v] += size[u]; rev[v] += rev[u] + (order ? 0 : 1); } } } void solve() { dfs(0); opt[0] = rev[0]; for (int v = 1; v < N; ++v) { opt[v] = rev[v]; opt[v] += (rev[0] - (depth[v] - ord[v]) - rev[v] + ord[v]); } int mini = N; for (int i = 0; i < N; ++i) { updateMin(mini, opt[i]); } vector<int> ans; ans.reserve(N); for (int i = 0; i < N; ++i) { if (opt[i] == mini) { ans.push_back(i); } } printf("%d\n", mini); for (int i = 0; i < (int)ans.size(); ++i) { printf("%d%c", ans[i] + 1, i==(int)ans.size()-1 ? '\n' : ' '); } } int main() { init(); solve(); return 0; }