1056.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1056 on 2005-12-21 at 01:17:16 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;

int n, m, k;
bool mach[MAX][MAX];
bool check[MAX];
int match[MAX];

bool DFS(int);

int main()
{
	int i;
	char line[MAX];
	
	while(gets(line) != NULL && strcmp(line, "0")) {
		if(line[0] == 0) continue;
		sscanf(line, "%d %d %d", &n, &m, &k);
		memset(mach, false, sizeof(mach));
		for(i = 0; i < k; i++) {
			int a, b;
			scanf("%*d %d %d", &a, &b);
			if(a*b != 0) {
				mach[a][b] = true;
			}
		}
		int cost = 0;
		memset(match, -1, sizeof(match));
		for(i = 0; i < n; i++) {
			memset(check, false, sizeof(check));
			if(DFS(i)) {
				cost++;
			}
		}
		printf("%d\n", cost);
	}
	
	return 0;
}

bool DFS(int p)
{
	int i, t;
	for(i = 0; i < m; i++) {
		if(mach[p][i] && !check[i]) {
			check[i] = true;
			t = match[i];
			match[i] = p;
			if(t == -1 || DFS(t)) {
				return true;
			}
			match[i] = t;
		}
	}
	return false;
}