これはコンテスト本番にて、すぐに解けてよかった
問題概要
個の単語 (いずれも英小文字) が与えられる。これらの単語の列が極大しりとりであると は、
- しりとりである
- しりとりの最後尾に続けられる単語がもう残っていない
ようなものを指す。ありうる極大しりとりを全部考えたときの、最後尾単語の最後の文字としてありうるものをすべて答えよ。
制約
解法
しりとりと言われると、
- 各ノードが各アルファベットに対応 (26 ノード)
- 各辺が各単語に対応 (N 辺)
という有向グラフを考えたくなる。ここで文字 c に着目すると、c で終わるためには、c から出ている辺をすべてつぶさなければならない。つまり、
- c から出ている辺はすべて c に帰ってこなければならない
ことがわかる。そして、c から出ている辺をすべて使い切った状態で c に帰って来れば、c で終わることができる。
これはつまり、c から出ている辺数を k として、c から入って c へ帰っていくグラフの edge-connectivity が k 以上かどうかを判定する問題となる。よって最大フローを流して、それが k 以上かどうかを判定すればよい。
#include <iostream> #include <queue> #include <vector> using namespace std; // edge class (for network-flow) template<class FLOWTYPE> struct Edge { int rev, from, to; FLOWTYPE cap, icap; Edge(int r, int f, int t, FLOWTYPE c) : rev(r), from(f), to(t), cap(c), icap(c) {} friend ostream& operator << (ostream& s, const Edge& E) { if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ')'; else return s; } }; // graph class (for network-flow) template<class FLOWTYPE> struct Graph { vector<vector<Edge<FLOWTYPE> > > list; Graph(int n = 0) : list(n) { } void init(int n = 0) { list.clear(); list.resize(n); } void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; } inline vector<Edge<FLOWTYPE> >& operator [] (int i) { return list[i]; } inline const size_t size() const { return list.size(); } inline Edge<FLOWTYPE> &redge(Edge<FLOWTYPE> e) { if (e.from != e.to) return list[e.to][e.rev]; else return list[e.to][e.rev + 1]; } void addedge(int from, int to, FLOWTYPE cap) { list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap)); list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0)); } void add_undirected_edge(int from, int to, FLOWTYPE cap) { list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap)); list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, cap)); } /* // debug friend ostream& operator << (ostream& s, const Graph& G) { s << endl; for (int i = 0; i < G.V; ++i) { s << i << " : " << G.list[i] << endl; }return s; } */ }; template<class FLOWTYPE> struct Dinic { const FLOWTYPE INF = 1<<30; // to be set vector<int> level, iter; Dinic() { } void dibfs(Graph<FLOWTYPE> &G, int s) { level.assign((int)G.size(), -1); level[s] = 0; queue<int> que; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (int i = 0; i < G[v].size(); ++i) { Edge<FLOWTYPE> &e = G[v][i]; if (level[e.to] < 0 && e.cap > 0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } FLOWTYPE didfs(Graph<FLOWTYPE> &G, int v, int t, FLOWTYPE f) { if (v == t) return f; for (int &i = iter[v]; i < G[v].size(); ++i) { Edge<FLOWTYPE> &e = G[v][i], &re = G.redge(e); if (level[v] < level[e.to] && e.cap > 0) { FLOWTYPE d = didfs(G, e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; re.cap += d; return d; } } } return 0; } FLOWTYPE solve(Graph<FLOWTYPE> &G, int s, int t) { level.assign((int)G.size(), -1); iter.assign((int)G.size(), 0); FLOWTYPE res = 0; while (true) { dibfs(G, s); if (level[t] < 0) return res; for (int i = 0; i < (int)iter.size(); ++i) iter[i] = 0; FLOWTYPE flow = 0; while ((flow = didfs(G, s, t, INF)) > 0) { res += flow; } } } }; int main() { int N; cin >> N; vector<string> S(N); S.resize(N); for (int i = 0; i < N; ++i) cin >> S[i]; vector<char> res; for (int ch = 0; ch < 26; ++ch) { Graph<int> G(28); int s = 26, t = 27; int deg_out = 0, deg_in = 0; for (int i = 0; i < N; ++i) { int u = S[i][0] - 'a'; int v = S[i].back() - 'a'; if (u == ch) u = s, ++deg_out; if (v == ch) v = t, ++deg_in; G.addedge(u, v, 1); } Dinic<int> din; int flow = din.solve(G, s, t); if (flow >= deg_out && deg_in > 0) res.push_back((char)('a' + ch)); } for (auto c : res) cout << c << endl; }