yukicoder : No.483 マッチ並べ

想定解が予想外すぎた…。
http://yukicoder.me/problems/no/483

問題

N個の長さ1のマッチ棒を2次元座標上に置くことを考える。
マッチ棒を置く位置は指定されており、2つの格子点を結ぶように配置する。
その際、どちらを頭にするかを指定できる。

その際、同じ格子点上に複数のマッチ棒の頭が来ないような向きの配置を取れるか判定せよ。

解法

想定解は、連結成分内に2つ以上の閉路があると条件を満たす配置ができないので、閉路を数えることらしい。

自分はマッチング問題とみなして最大フローで解いた。
source、sinkに加え、マッチ棒に相当するN個の頂点と、座標上の格子点からなるグラフを考える。
以下のようにそれぞれ容量1の辺を張り、最大フローがNなら条件を満たせる。

• source→マッチ棒に相当するN頂点
• マッチ棒に相当する頂点→2つの配置先の格子点に相当する頂点
• 各格子点に相当する頂点→sink

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 20500;
	vector<edge> E[MV];
	int vis[MV];
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	V dfs(int from,int to,V cf) {
		V tf;
		if(from==to) return cf;
		vis[from]=1;
		FORR(e,E[from]) if(vis[e.to]==0 && e.cap>0 && (tf = dfs(e.to,to,min(cf,e.cap)))>0) {
			e.cap -= tf;
			E[e.to][e.reve].cap += tf;
			return tf;
		}
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,numeric_limits<V>::max()))==0) return fl;
			fl+=tf;
		}
	}
};

int N;
int X1[101],X2[101],Y1[101],Y2[101];
MaxFlow_Ford<int> mf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,104) FOR(x,104) mf.add_edge(y*105+x,105*105,1);
	
	
	FOR(i,N) {
		cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
		
		mf.add_edge(105*106,106*106+i,1);
		mf.add_edge(106*106+i,X1[i]*105+Y1[i],1);
		mf.add_edge(106*106+i,X2[i]*105+Y2[i],1);
	}
	x = mf.maxflow(105*106,105*105);
	if(x==N) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	
}

まとめ

マッチ棒とマッチングを掛けた問題だと勘違いしました。
Union-Find解とかオイラーの定理とか頭よすぎじゃないですかね。
ほかの人であんまり最大フローに持ち込んでる人はいない…？