asteroids(二分图最小顶点覆盖).cpp

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

//构造二分图，X为行，Y为列，即求二分图最小顶点覆盖
//Bi-partitte Graph's the mininum vertex cover = the maxinum match
#include<cstdio>
#include<memory>
#include<vector>
using namespace std;

const int Max = 510;
vector< vector<int> > Bmap;
int n, m, k, nm;
int mark[Max];
bool flag[Max];
bool map[Max][Max];

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

inline int Max_Match()
{
	int mmax = 0, i;
	for(i=1; i <= n ;i++) {
		memset(flag,0,sizeof(flag));
		if( dfs(i) ) {
			mmax++;
		}
	}
	return mmax;
}

int main()
{
	int i, j, r, c, t;
	
	while (scanf("%d %d", &n, &k) ==2) {
		Bmap.clear();
		Bmap.resize(n+10);
		memset(mark,-1,sizeof(mark));
		memset(map,0,sizeof(map));
		for(i=0; i < k ;i++) {
			scanf("%d %d", &r, &c);
			map[r][c] = true;
		}
		for(i=1; i <= n ;i++) {
			for(j=1; j <= n ;j++) {
				if(map[i][j]) {
					Bmap[i].push_back(j);
				}
			}
		}
		printf("%d\n", Max_Match());
	}
}