uncle tom's inherited land(二分匹配).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 110 
#define PMAX 60

int n, m, k, p;
struct node {
	int x,y;
}point[PMAX];
int graph[NMAX][NMAX];
vector< vector<int> > Bmap;
int mark[PMAX];
bool flag[PMAX];

bool dfs(int pos)
{
	int i,l;
	l = Bmap[pos].size();
	for(i=0;i<l;i++) {
		int tp = Bmap[pos][i];
		if(!flag[tp]) {
			flag[tp] = true;
			int pre = mark[tp];
			mark[tp] = pos;
			if(pre == -1 || dfs(pre)) {
				return true;
			}
			mark[tp] = pre;
		}
	}
	return false;
}

int Max_Match()
{
	int i, mmax;
	mmax = 0;
	for(i=0;i<p;i++) {
		memset(flag,0,sizeof(flag));
		if((point[i].x+point[i].y)%2==0 && dfs(i)) {//以奇偶性划分二分图
			mmax ++;
		}
	}
	return mmax;
}

int main()
{
	int i,j,x,y;

	while(scanf("%d %d",&n,&m)==2) {
		if(n==0 && m==0) {
			break;
		}
		scanf("%d", &k);
		memset(graph, 0, sizeof(graph));
		for(i=0;i<k;i++) {
			scanf("%d %d", &x,&y);
			x--; y--;
			graph[x][y] = -1;
		}
		for(i=0;i<m;i++) {
			graph[n][i] = -1;
		}
		for(i=0;i<n;i++) {
			graph[i][m] = -1;
		}

		p = 0;
		for(i=0;i<n;i++) {
			for(j=0;j<m;j++) {
				if(graph[i][j] != -1) {
					point[p].x = i+1;
					point[p].y = j+1;
					graph[i][j] = p ++;
				}
			}
		}
		Bmap.clear();
		Bmap.resize(p + 10);
		for(i=0;i<n;i++) {
			for(j=0;j<m;j++) {
				if(graph[i][j] != -1) {
					if(graph[i+1][j] != -1) {
						Bmap[ graph[i][j] ].push_back( graph[i+1][j] );
						Bmap[ graph[i+1][j] ].push_back( graph[i][j] );
					}
					if(graph[i][j+1] != -1) {
						Bmap[ graph[i][j] ].push_back( graph[i][j+1] );
						Bmap[ graph[i][j+1] ].push_back( graph[i][j] );
					}
				}
			}
		}
		memset(mark,-1,sizeof(mark));
		printf("%d\n", Max_Match());
		for(i=0;i<p;i++) {
			if(mark[i] >= 0) {
				mark[ mark[i] ] = -1;
				printf("(%d,%d)--(%d,%d)\n", point[i].x, point[i].y, point[mark[i]].x, point[mark[i]].y);
			}
		}
		printf("\n");
	}
}