LiveArchive 5874 Social Holidaying
問題
一般グラフにおいて辺数最大マッチングのサイズを求めよ。
解法
蟻本P198や組合せ最適化P271 系10.9 に載っているTutte行列を用いて最大マッチングを求めるLovaszのランダム化アルゴリズムを使う。 別の解法としては、Edmondsの辺数最大マッチングアルゴリズム(Cardinality Matching Algorithm)を投げるものがある。
Lovaszのランダム化アルゴリズムは、以下の定理に基づく。
定理(Tutte[1947])
が完全マッチングを持つための必要十分条件は、が恒等的に零ではないことである。
Tutte行列は変数を要素としている。行列の行列式は計算が難しいが、この変数に一様な乱数を与えることで、十分な確率で最大マッチングの頂点数が求まる。
具体的には、の正方行列に対して辺が張られている要素に歪対称()にの範囲で一様な乱数を設定し、他の要素の値はとして行列のランクを求めると、辺数最大マッチングのサイズの2倍(最大マッチングの頂点数)となる。よって、これを2で割った値が答えとなる。
一様な乱数なので、srand(), rand()を使わずにrandom_device, mt19937, uniform_real_distributionを使った方がいい感じにACした。行列のランクを求めるコードは他の人のコードを参考にした。
ところで、Tutte行列なので歪対称にする必要があると思うのだが、そうした場合はそこそこWAになる。歪対称にせずにとを別々のランダムな値にすると常にACする。テストケースがおかしいのか自分が勘違いしているのかがわからない。
また、組合せ最適化P271によると、乱数としての範囲の実数ではなく十分大きなを選んで有限集合からランダムに整数を選んできても良いはずなのだが、よくわからない理由(行列計算のオーバーフローなどだろうか?)でしばしばWAになったので、実数乱数を用いた。
namespace flow { class maximum_matching { private: using number = double; using vec = vector<number>; using mat = vector<vec>; double const EPS = 1e-8; random_device seed_gen; mt19937_64 mt; uniform_real_distribution<number> dist; mat A; int mrank(){ const int N = A.size(); int rank = 0; mat B(N, vec(N+1, 1)); for(int i=0; i<N; i++) for(int j=0; j<N; j++) B[i][j] = A[i][j]; for(int i=0; i<N; i++) { int pivot = i; for(int j=i; j<N; j++) { if(abs(B[j][i]) > abs(B[pivot][i])) pivot = j; } swap(B[i], B[pivot]); if(abs(B[i][i]) < EPS) continue; for(int j=i+1; j<N+1; j++) B[i][j] /= B[i][i]; for(int j=0; j<N; j++) if(i != j) for(int k=i+1; k<N+1; k++) B[j][k] -= B[j][i] * B[i][k]; rank ++; } return rank; } public: maximum_matching(int V) : mt(seed_gen()), dist(0, 1) { A.resize(V); for(int i=0; i<V; i++) A[i].resize(V); } void add_edge(int u, int v) { A[u][v] = dist(mt); A[v][u] = dist(mt); } int maximum_matching_number() { return mrank() / 2; } }; } int main() { int Tc; cin >> Tc; while(Tc--) { int N, M; cin >> N >> M; vector<int> A(N); for(int i=0; i<N; i++) cin >> A[i]; set<int> able; for(int i=0; i<M; i++) { int x; cin >> x; able.insert(x); } flow::maximum_matching mm(N); for(int i=0; i<N; i++) for(int j=i+1; j<N; j++) { if(i == j) continue; if(able.count(A[i] + A[j])) mm.add_edge(i, j); } cout << mm.maximum_matching_number() << endl; } return 0; }