こうきさんに聞いて解いてみた。
木を最小個数のパスで被覆する問題はとりあえず2種類あって、辺の重複ありの場合は昨日のCSA 069 D. Cover the Treeで適切に葉同士で繋ぐ感じにする。辺の重複無しの場合は奇数次の点に適当に辺を張ってオイラー閉路作って切っていくやつで、これは木ではなくてもよくて実質 CSA 061 F. Xor the Graph
— こうきやまぐち (@Ymgch_K) 2018年2月15日
N 頂点 M 辺の無向グラフが与えられる。
各辺には 0 または 1 の数字が振られている。今、このグラフのウォークを選んで、ウォーク上の辺の値を flip する操作を行う。最小回数の操作ですべての辺の値を 0 にせよ。
- 1 <= N, M <= 105
注: 問題文にパスと書いてあるが、同じ頂点を二度訪れていいので厳密にはパスではない
以下のことが言える
- 1 の辺はちょうど 1 回被覆されるとしてよい (3 回被覆した解を本数変えずに変形できる)
- 0 の辺はちょうど 2 回被覆されるとしてよい (0 回被覆した解を本数変えずに変形できる)
よって、0 の辺を二重辺とした無向グラフの辺を重複を許さずに最小本数のウォークで 1 回ずつ被覆する問題になる。
これはなんとオイラー閉路を考えることで解くことができる！
まず、連結成分ごとに考えることにする。よってグラフを連結と仮定してよい。自明な下界として、(奇数次数の頂点数) / 2 が言える。奇数次数の頂点はウォークの端点とせざるをえないからだ。
さらに、これが実際に達成できることが言える！！！これがすごい。 奇数次数の頂点は必ず偶数個なのでテキトーに2個ずつペアにして辺で結ぶと、オイラーグラフになる。このオイラーグラフでオイラー閉路を求め、さっき張った辺の部分を除去して切断すれば、(奇数次数の頂点数) / 2 本のウォークになり、これが答え。
#include <iostream> #include <vector> #include <map> #include <cstring> #include <algorithm> using namespace std; /* 枝 */ struct Edge { int rev, from, to, cap; Edge(int r, int f, int t, int c) : rev(r), from(f), to(t), cap(c) {} }; /* グラフ */ const int MAX_V = 110000; struct Graph { int V; vector<Edge> list[MAX_V]; Graph(int n = 0) : V(n) {for (int i = 0; i < MAX_V; ++i) list[i].clear();} inline vector<Edge>& operator [] (int i) {return list[i];} inline Edge &redge(Edge 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, int cap) { list[from].push_back(Edge(list[to].size(), from, to, cap)); list[to].push_back(Edge(list[from].size()-1, to, from, cap)); } }; /* オイラー路を求める */ int contin[MAX_V]; void Edfs(Graph &G, int v, vector<int> &walk) { for (int &i = contin[v]; i < G[v].size(); ++i) { Edge &e = G[v][i]; if (e.cap > 0) { --e.cap; --G.redge(e).cap; Edfs(G, G[v][i].to, walk); } } walk.push_back(v); } vector<int> EulerTour(Graph &G, int s = 0) { vector<int> res; Edfs(G, s, res); reverse(res.begin(), res.end()); return res; } /* 入力情報 */ int N, M; int deg[MAX_V]; // 次数 /* 元のグラフを連結成分に分ける */ bool seen[MAX_V]; vector<int> odds; bool allzero = true; void dfs(Graph &G, int v) { seen[v] = true; for (auto ad : G[v]) { if (ad.cap == 1) allzero = false; if (seen[ad.to]) continue; dfs(G, ad.to); } if (deg[v] & 1) odds.push_back(v); } /* main */ int main() { cin >> N >> M; Graph G(N); memset(deg, 0, sizeof(deg)); for (int i = 0; i < M; ++i) { int a, b, c; cin >> a >> b >> c; --a, --b; if (c == 0) { G.addedge(a, b, 2); deg[a] += 2; deg[b] += 2; } else { G.addedge(a, b, 1); deg[a]++; deg[b]++; } } memset(seen, 0, sizeof(seen)); memset(contin, 0, sizeof(contin)); vector<vector<int> > walks; for (int v = 0; v < N; ++v) { if (seen[v]) continue; odds.clear(); allzero = true; dfs(G, v); /* 連結成分が全部 0 だったら何もしない */ if (allzero) continue; /* 加える辺 */ map<pair<int,int>, int> adds; for (int i = 0; i < odds.size(); i += 2) { adds[make_pair(odds[i], odds[i+1])]++; adds[make_pair(odds[i+1], odds[i])]++; G.addedge(odds[i], odds[i+1], 1); } vector<int> euler = EulerTour(G, v); // 奇数次頂点がなかったらオイラー路そのもの if (odds.size() == 0) { walks.push_back(euler); continue; } // cut euler.pop_back(); int start = 0; // cut の切れ目のスタート地点 for (int i = 1; i <= euler.size(); ++i) { if (adds[make_pair(euler[i-1], euler[i%euler.size()])] > 0) { start = i; break; } } adds[make_pair(euler[start-1], euler[start%euler.size()])]--; adds[make_pair(euler[start%euler.size()], euler[start-1])]--; vector<int> tmp; tmp.push_back(euler[start%euler.size()]); for (int i = 0; i+1 < euler.size(); ++i) { int j = (i+start) % euler.size(); int k = (j+1) % euler.size(); if (i > 0 && adds[make_pair(euler[j], euler[k])] > 0) { walks.push_back(tmp); tmp.clear(); tmp.push_back(euler[k]); adds[make_pair(euler[j], euler[k])]--; adds[make_pair(euler[k], euler[j])]--; } else { tmp.push_back(euler[k]); } } if (tmp.size() > 1) walks.push_back(tmp); } cout << walks.size() << endl; for (int i = 0; i < walks.size(); ++i) { cout << walks[i].size(); for (int j = 0; j < walks[i].size(); ++j) { cout << " " << walks[i][j] + 1; } cout << endl; } }
