POJ-1486, LiveArchive-5634, UVa-663, ZOJ-1197, TJU-1611 : Sorting Slides

問題概要

片方のサイズ26以下の二部グラフが与えられる。完全マッチングを作るときに一位に定まるものを出力する問題。

解法

全てのペアに対して、一度固定してから残りを使って完全マッチングができるかどうかを判定すればよい。二部マッチングは差分のみ計算とかできるので頑張れば高速化できるけど、サイズが小さいので愚直にやって間に合う。

acceptされたコード

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 26;

struct BipartiteMatching{
	static const int MAX_V = ::MAX_N * 2;
	int V;
	vector<int> graph[MAX_V];
	bool visited[MAX_V];
	int match[MAX_V];

	void clear(){
		for(int i=0; i<MAX_V; ++i){
			graph[i].clear();
		}
	}

	void add_edge(int u, int v){
		graph[v].push_back(u);
		graph[u].push_back(v);
	}

	bool dfs(int v){
		visited[v] = true;
		for(int i=0; i<(int)graph[v].size(); ++i){
			const int u = graph[v][i], w = match[u];
			if(w < 0 || (!visited[w] && dfs(w))){
				match[u] = v;
				match[v] = u;
				return true;
			}
		}
		return false;
	}

	int bipartite_matching(){
		int ret = 0;
		memset(match, -1, sizeof(match));
		for(int v=0; v<V; ++v){
			if(match[v] < 0){
				memset(visited, false, sizeof(visited));
				if(dfs(v)){
					ret++;
				}
			}
		}
		return ret;
	}

	void set_V(int V_){
		V = V_;
	}
};

BipartiteMatching bm;

int N;
int xs[MAX_N][2], ys[MAX_N][2];
int xx[MAX_N], yy[MAX_N];

bool init(){
	scanf("%d", &N);
	for(int i=0; i<N; ++i){
		scanf("%d%d%d%d", xs[i]+0, xs[i]+1, ys[i]+0, ys[i]+1);
	}
	for(int i=0; i<N; ++i){
		scanf("%d%d", xx+i, yy+i);
	}
	return N > 0;
}

bool contain(int i, int j){
	return xs[i][0] < xx[j] && xx[j] < xs[i][1] && ys[i][0] < yy[j] && yy[j] < ys[i][1];
}

void solve(){
	int match[MAX_N];
	memset(match, -1, sizeof(match));

	for(int i=0; i<N; ++i){
		int match_count = 0;
		for(int k=0; k<N; ++k)if(contain(i, k)){
			bm.clear();
			bm.set_V(2*N);
			for(int j=0; j<N; ++j)if(i!=j){
				for(int l=0; l<N; ++l)if(k!=l){
					if(contain(j, l)){
						bm.add_edge(j, l+N);
					}
				}
			}
			if(bm.bipartite_matching() == N - 1){
				++match_count;
				match[i] = k;
			}
		}
		if(match_count != 1){
			match[i] = -1;
		}
	}

	bool ok = false;
	for(int i=0; i<N; ++i)if(match[i]!=-1){
		printf("%s(%c,%d)", (ok?" ":""),  i+'A', match[i] + 1);
		ok = true;
	}
	if(ok){
		puts("");
	}
	else{
		puts("none");
	}
}

int main(){
	for(int i=0; init(); ++i){
		printf("Heap %d\n", i+1);
		solve();
		puts("");
	}
}