アルファベットは 26 文字!26 は偶数!
問題概要 (意訳)
頂点数 、辺数 の無向単純グラフ が与えられる。各頂点 には、1 文字の英小文字 が振られている。ここで正の整数 が与えられ、改めて次のように定義されるグラフ を考える
- の頂点集合は に一致する
- 頂点 間に辺が張られる条件は、以下の 2 つをともに満たすことである
- と が隣接する英小文字である ('z' と 'a' は隣接しているとみなす)
- 頂点 は 上で 本以下の辺をたどって行き来できる
このように新たに作られたグラフ 上の最小頂点被覆のサイズを求めよ。
制約
考えたこと
一般にグラフの最小頂点被覆問題は NP 困難であって解けない。しかし特殊なグラフでは解けることもある。一例として「二部グラフ」がある。二部グラフ上の最小頂点被覆問題を解く方法については、次の記事を参照。
今回のグラフは、そもそも「隣接しているアルファベット間にしか辺がない」ことに着目する。次のように、二部グラフであることがわかる!
- 左側ノード:アルファベットが a, c, e, g, ... である頂点
- 右側ノード:アルファベットが b, d, f, h, ... である頂点
アルファベットは 26 種類なので、左右に綺麗に分離できる。そして左側頂点同士には辺がなく、右側頂点同士にも辺がない。
よって、グラフ が二部グラフであることがわかった。具体的な辺の張り方については、元のグラフ 上で Floyd-Warshall 法によって全頂点間の最短距離を求め、それが 以下であるところに辺を張れば OK。計算量は 。
コード
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } struct HopcroftKarp { int sizeL, sizeR; vector<vector<int> > list; // left to right // result vector<bool> seen, matched; vector<int> level, matching; // base HopcroftKarp(int l, int r) : sizeL(l), sizeR(r), list(l, vector<int>()) { } inline vector<int>& operator [] (int i) { return list[i]; } inline void addedge(int from, int to) { list[from].push_back(to); } inline friend ostream& operator << (ostream& s, const HopcroftKarp& G) { s << endl; for (int i = 0; i < G.list.size(); ++i) { s << i << " : "; for (int j = 0; j < G.list[i].size(); ++j) { s << G.list[i][j]; if (j + 1 != G.list[i].size()) s << ", "; } s << endl; } return s; } // methods void hobfs() { queue<int> que; for (int left = 0; left < sizeL; ++left) { level[left] = -1; if (!matched[left]) { que.push(left); level[left] = 0; } } level[sizeL] = sizeL; while (!que.empty()) { int left = que.front(); que.pop(); for (int i = 0; i < list[left].size(); ++i) { int right = list[left][i]; int next = matching[right]; if (level[next] == -1) { level[next] = level[left] + 1; que.push(next); } } } } bool hodfs(int left) { if (left == sizeL) return true; if (seen[left]) return false; seen[left] = true; for (int i = 0; i < list[left].size(); ++i) { int right = list[left][i]; int next = matching[right]; if (level[next] > level[left] && hodfs(next)) { matching[right] = left; return true; } } return false; } int solve() { seen.assign(sizeL, false); matched.assign(sizeL, false); level.assign(sizeL+1, -1); matching.assign(sizeR, sizeL); int res = 0; while (true) { hobfs(); seen.assign(sizeL, false); bool finished = true; for (int left = 0; left < sizeL; ++left) { if (!matched[left] && hodfs(left)) { matched[left] = true; ++res; finished = false; } } if (finished) break; } return res; } }; const long long INF = 1LL<<59; int main() { int N, M, K; cin >> N >> M >> K; vector<int> C(N); for (int i = 0; i < N; ++i) { char ch; cin >> ch; C[i] = ch - 'a'; } // Floyd-Warshall vector<vector<long long>> D(N, vector<long long>(N, INF)); for (int i = 0; i < N; ++i) D[i][i] = 0; for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; --u, --v; D[u][v] = 1, D[v][u] = 1; } for (int k = 0; k < N; ++k) for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) chmin(D[i][j], D[i][k] + D[k][j]); // Hopcroft-Karp vector<int> left, right; for (int i = 0; i < N; ++i) { if (C[i] % 2 == 0) left.push_back(i); else right.push_back(i); } HopcroftKarp G(left.size(), right.size()); for (int i = 0; i < left.size(); ++i) { for (int j = 0; j < right.size(); ++j) { int u = left[i], v = right[j]; int dist = (C[v] - C[u] + 26) % 26; if (D[u][v] <= K && (dist == 1 || dist == 25)) G.addedge(i, j); } } cout << G.solve() << endl; }