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

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

//Bi-partitte Graph's the mininum vertex cover = the maxinum match
#include<cstdio>
#include<memory>
#include<vector>
using namespace std;

const int Max = 210;
vector< vector<int> > Bmap;
int n, m, k, nm;
int mark[Max];
bool flag[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=0; i < n ;i++) {
		memset(flag,0,sizeof(flag));
		if( dfs(i) ) {
			mmax++;
		}
	}
	return mmax;
}

int main()
{
	int i, j, id1, id2;
	while(scanf("%d", &n), n) {
		scanf("%d %d", &m, &k);
		nm = n+m;
		Bmap.clear();
		Bmap.resize(nm+10);
		memset(mark,-1,sizeof(mark));

		for(i=0; i < k ;i++) {
			scanf("%d %d %d", &j, &id1, &id2);
			if (id1 != 0 && id2 != 0) {//machine start at mode 0
				Bmap[id1].push_back(id2+n);
			}
		}
		printf("%d\n", Max_Match());
	}
}