H: Animal Companion in Maze
問題
グラフが与えられる。辺は有向のものと無向（双方向）のものがある。長さは全て1。
無向辺を通ったときにすぐ同じ辺を引き返してはならないとき、最長歩道の長さを出力せよ。
歩道とは頂点・辺の重複を許したパスのこと。
答えを無限に大きくできる場合はInfiniteと出力せよ。
制約
n <= 100000
m <= 100000
解法
まずInfiniteを判定する。無向グラフのサイクル判定は素集合データ構造でクラスカル法のように辺を繋ぐのが簡単。有向グラフのサイクル判定はトポロジカルソートが簡単。
最長歩道のパートは、サイクルがないので点素な最長パスを求めることに成る。深さ優先探索のDPを再帰関数で実装する。各辺に対して最長歩道の長さをメモするだけでは次数の大きい頂点で計算が大きくなる。往復する木DP（全方位木DPと呼ばれたりするかも）のように、辺のdpの値を並べて累積最大値（fold max）を左右から取ればよい。
最初は全てinfで初期化されている（図左）。dfsの計算で無向辺を使ってcからvに来たとき、v->a / v->b / v->d / v->e と再帰的に最長パスを求め、累積最大値のテーブルを作る（図中）。その後、また別のところからvに入ってきたらv->cだけ再帰的に求め、累積最大値のテーブルを更新する。テーブルが完成したので以降dfsはvの先に進むことはない。
計算量はDSUがO(a n + m)、DFSがO(n + m)、全体でO(a n + m)。
コード
#include<queue> #include<stdio.h> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<string.h> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(s...) fprintf(stderr, s) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } #define left TWILIGHT_SKY #define right SPARKLING_GIRL struct UnionFind { int n; vector<int> U; UnionFind() {} UnionFind(int n): n(n), U(n, -1) {} int root(int x) { if (U[x] < 0) return x; return U[x] = root(U[x]); } int link(int x, int y) { x = root(x); y = root(y); if (x == y) return x; if (U[y] < U[x]) swap(x, y); U[x] += U[y]; n--; return U[y] = x; } bool same(int x, int y) { return root(x) == root(y); } int size() { return n; } int count(int x) { return -U[root(x)]; } }; struct Edge { int to; int rev; Edge() {} Edge(int to_, int rev_) : to(to_), rev(rev_) {} }; int N, M; vector<Edge> G[100111]; vector<int> left[100111], just[100111], right[100111]; const int INF = 1<<29; VI D[100111]; int deg[100111]; vector<pair<int, int> > edges, arcs; int dfs(int v, int back) { if (back != -1) { int tmp = max(left[v][back], right[v][back+1]); if (tmp != INF) return tmp; } if (right[v][0] == INF) { REP (i, G[v].size()) { if (i == back || just[v][i] != INF) { // nothing } else { int tmp = dfs(G[v][i].to, G[v][i].rev); just[v][i] = tmp + 1; } } REP (i, G[v].size()) left[v][i+1] = max(left[v][i], just[v][i]); for (int i=G[v].size(); i--; ) right[v][i] = max(right[v][i+1], just[v][i]); } if (back == -1) return right[v][0]; else return max(left[v][back], right[v][back+1]); } int main() { scanf("%d%d", &N, &M); REP (i, M) { int x, y, w; scanf("%d%d%d", &x, &y, &w); x--; y--; if (w == 1) { G[x].push_back(Edge(y, -1)); arcs.push_back(make_pair(x, y)); } else { G[x].push_back(Edge(y, G[y].size())); G[y].push_back(Edge(x, G[x].size()-1)); edges.push_back(make_pair(x, y)); } } bool inf = false; // check undirected cycle UnionFind U(N); EACH (e, edges) { if (U.same(e->first, e->second)) { inf = true; break; } U.link(e->first, e->second); } // check directed cycle if (!inf) { EACH (e, arcs) { int x = e->first, y = e->second; D[U.root(x)].push_back(U.root(y)); deg[U.root(y)]++; } VI ord; REP (i, N) if (deg[i] == 0) ord.push_back(i); for (int i_=0; i_<(int)ord.size(); i_++) { int v = ord[i_]; EACH (e, D[v]) { deg[*e]--; if (deg[*e] == 0) ord.push_back(*e); } } if ((int)ord.size() != N) { inf = true; } } // main solution if (!inf) { int ans = 0; REP (i, N) { int l = G[i].size(); just[i].assign(l, INF); left[i].assign(l+1, INF); right[i].assign(l+1, INF); left[i][0] = right[i][l] = 0; } REP (i, N) { int tmp = dfs(i, -1); amax(ans, tmp); } printf("%d\n", ans); } else { puts("Infinite"); } return 0; }
感想
グラフの問題の数に対して、有向と無向が混ざったものは少ない。特に、無向を有向辺2つに置き換えることができないものは珍しい。
無限ループの判定をdpの計算でdfsしながらやろうとしたら難しくてできなかった。
本コンテストの中で一番おもしろい問題。
往復木DP時々見るが過去問思い出せない。距離を求めるだけなので往復木DPは必要ないかもしれないので、いい方法あったら教えて。
