AOJ 2347: Sunny Graph

教育的良問。是非解くことをおすすめします。

まず、一般グラフの完全マッチングの存在判定におけるTutteの定理を説明します。
Tutteの定理とは、無向グラフから作られる|V|×|V|のTutte行列((i,j)間に辺があるときはA[i][j]+A[j][i]=0となるように変数を、辺がないときはA[i][j]=A[j][i]=0と定数を置いた行列)に対して、
この行列式に生き残った項がある ⇔ 完全マッチングを持つ
ということが成り立つ定理です。

以下、簡単な証明です。
まず、置換を使う行列式の定義の式の各項を考えます。
各項は、置換のところが「複数個のサイクルで構成された部分グラフ」に対応します。(SRMのCurvyOnRailsとかを参照)
まず、完全マッチングがある場合、完全マッチングに対応する項は消せません。なぜなら1つの完全マッチングにはx^2みたいな2乗の項からなるものが対応し、これはそれぞれ1通りしかないからです。
そうでないとき、長さ3以上の閉路が存在することになります。これに対応するのが複数通りあるというのは、サイクルを逆向きにすることに対応しています。
長さ3以上の閉路については、
長さ偶数の閉路に対応する項が生き残っているとしても、長さ偶数の閉路だけなら完全マッチングを作ることができるので問題なしです。
長さ奇数の閉路は、そのうち1つ閉路を逆向き(厳密には1対1対応を取るために、複数個あるときは一番頂点番号の小さいものだけを逆向きにします)にすると、まず置換ではないほうの掛け算は、マイナスの個数の偶奇が変わるので-1倍となります。転倒数は、末尾2つを先頭2つに移動させたもので、これは偶奇が変わりません。すなわちこの組を足すと0になります。
よって行列式が0となるときは長さ2の閉路完全マッチングは作れません。

多項式の0判定は実際にランダムな値を代入する乱択で上手く解けることが知られています。

この定理を少しいじくればSunny Graphは解けます。
常に閉路には頂点1が含まれているので、頂点1から出る2本の辺の符号を、辺の向きを逆にしたものと相殺されないように決めたいです。
要は、頂点1から出る辺のうち片方は A[i][j]=A[j][i]で、もう片方が A[i][j]=-A[j][i]となるようにできたとします。
残りはTutte行列と同様にすると、
この行列式に生き残った項がある ⇔ Sunny Graphである
ということがいえます。

さっきの「できたとします。」と言っているところの「できる」確率はランダムにA[i][j]=A[j][i]かA[i][j]=-A[j][i]としてしまえば 1/2 以上なので、多項式の0判定で実際にランダムな値を代入するのと同時にこの符号もランダムに決めてしまえば、同じように上手く解けます。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int g[210][210];
double mat[210][210];
inline double ABS(double a){return max(a,-a);}
double EPS=1e-9;
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;
		scanf("%d%d",&p,&q);
		p--;q--;
		g[p][q]=g[q][p]=1;
	}
	int TM=30;
	while(TM--){
		for(int i=0;i<a;i++){
			for(int j=i;j<a;j++){
				if(!g[i][j]){
					mat[i][j]=mat[j][i]=0;
				}else{
					mat[i][j]=(double)(rand()%1000000000)/1000000000;
					if(i==0&&rand()%2==0)mat[j][i]=mat[i][j];
					else mat[j][i]=-mat[i][j];
				}
			}
		}
		bool zero=false;
		for(int i=0;i<a;i++){
			int at=i;
			for(int j=i+1;j<a;j++){
				if(ABS(mat[at][i])<ABS(mat[j][i])){
					at=j;
				}
			}
			if(ABS(mat[at][i])<EPS){
				zero=true;break;
			}
			for(int j=0;j<a;j++){
				swap(mat[at][j],mat[i][j]);
			}
			for(int j=0;j<a;j++){
				if(i==j)continue;
				double ks=mat[j][i]/mat[i][i];
				for(int k=0;k<a;k++)mat[j][k]-=ks*mat[i][k];
			}
		}
		if(!zero){
			printf("Yes\n");return 0;
		}
	}
	printf("No\n");
}