[AtCoder] ABC 126 D – Even Relation
問題
方針
最小共通祖先
根から 頂点 \( i \) までの距離を \(d_i \) とすると、頂点 \( u \) と 頂点 \( v \) の距離は、\( u \) と \( v \) の最小共通祖先までの距離 \( lca(u, v) \) を用いて、\( d_u + d_v – 2lca(u, v) \) で表せるそうです。参考として、競技プログラミングにおけるLAC問題で言及されていました。
ある頂点からの距離
上記の事実を利用すると、同じ色に塗った頂点間の距離が偶数ということは、ある頂点から同じ色の別の頂点までの距離が偶数ということです。全ての頂点間の距離を調べる必要はなく、一つの頂点からの距離を調べるだけでよいです。また、ある頂点からの距離が奇数の場合、その頂点は別の色で塗れば良いです。
例えば、頂点 \( 1 \) を基準として、全ての頂点の距離をしらべ、その距離が偶数であれば、\( 1 \) と同じ色、そうでなければ違う色にします。どう距離を求めるかですが、僕はダイクストラ法を用いて解きました。
コード
提出したコード (Java)
ダイクストラ法をC++で書き直したものを後で追加しようと思います。
提出したコード (C++)
ダイクストラ法
typedef long long ll; static const ll INF = 100000000000000; struct Node { int id; ll cost; Node() {} Node(int id, ll cost) : id(id), cost(cost){} bool operator< (const Node& node) const { return node.cost < cost; } }; // N: 頂点数, E: 辺の数, d: 距離 を格納する配列, // t: 始点, flag: true なら 無向辺, false なら 有向辺 void dijkstra(int N, int E, ll d[], int t, int from[], int to[], ll cost[], bool flag) { static const int WHITE = 0; static const int GRAY = 1; static const int BLACK = 2; int color[N]; vector<Node> adj[N]; for (int i = 0; i < N; i++) { d[i] = INF; color[i] = WHITE; } // 隣接リストの作成 for (int i = 0; i < E; i++) { adj[from[i]].push_back(Node(to[i], cost[i])); if (flag) adj[to[i]].push_back(Node(from[i], cost[i])); } priority_queue<Node> pq; d[t] = 0; pq.push(Node(t, 0)); while (!pq.empty()) { Node f = pq.top(); pq.pop(); int u = f.id; color[u] = BLACK; if (d[u] < f.cost) continue; for (int j = 0; j < adj[u].size(); j++) { int v = adj[u][j].id; if (color[v] == BLACK) continue; if (d[v] > d[u] + adj[u][j].cost) { d[v] = d[u] + adj[u][j].cost; pq.push(Node(v, d[v])); color[v] = GRAY; } } } }
ディスカッション
コメント一覧
まだ、コメントがありません