记录编号	269295	评测结果	AAAAAAAAAA
题目名称	机器调度	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2016-06-13 14:17:50	内存使用	0.26 MiB

#include<cstdio>
#include<bits/stdc++.h>
using namespace std;

int Read()
{
	int a = 0, minus = 1;
	char ch = getchar();
	if(ch == '-')       minus = -1;
	while(ch < '0' || ch > '9'){
		ch = getchar();
		if(ch == '-')	minus = -1;
	}
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
	return a * minus;
}

int n, m, k;
bool beside[110][110] = {false}, visited[110] = {false};//beside[i][j] == true,说明i,j可以匹配,visited[i]表示是否用过i 
int a[110], b[110];//a[i] == j表示集合modea中i匹配集合modeb中j 

int Path(int x)
{
	for(int i = 1; i <= m; i++){
		if(beside[x][i] && !visited[i]){
			visited[i] = true;
			if(b[i] == -1 || Path(b[i])){
				//modeb中元素未匹配,或已经匹配但可以增广 
				b[i] = x;
				a[x] = i;
				return true;
			}
		} 
	}
	return false;
}

int main()
{
	freopen("machine.in", "r", stdin);
	freopen("machine.out", "w", stdout);
	memset(a, -1, sizeof(a)); memset(b, -1, sizeof(b));
	n = Read(), m = Read(), k = Read();
	for(int i = 1; i <= k; i++){
		int job = Read(), modea = Read(), modeb = Read();
		beside[modea][modeb] = true;//有向无环 
	}
	int ans = 0;
	
	for(int i = 1; i <= n; i++){
		if(a[i] == -1){//还未被匹配
			memset(visited, false, sizeof(visited));//重置 
			ans +=  Path(i);
		}
	}
	
	printf("%d", ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3

3

2 2 1
0 1 0

0
*/