记录编号	270693	评测结果	AAAAAAAAAA
题目名称	机器调度	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-06-15 10:19:31	内存使用	0.00 MiB

//求二分图最大匹配的匈牙利算法
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210;
struct edge{
	int to;
	edge* prev;
	edge():to(0),prev(NULL){}
}ee[2*maxn*maxn];
void insert(int,int);
bool path(int);
int maxmatch();
int len=0;
edge* last[maxn]={NULL};
int na,nb;//a集合和b集合中顶点的个数
int ca[maxn]={0},cb[maxn]={0};//用来记录匹配的元素是哪个
bool vis[maxn];
int x,y,m,ans;
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("machine.in","r",stdin);
	freopen("machine.out","w",stdout);
#endif
	scanf("%d%d%d",&na,&nb,&m);
	while(m--){
		scanf("%*d%d%d",&x,&y);
		if(x&&y)insert(x,y);
	}
	ans=maxmatch();
	if(cb[0])ans--;
	printf("%d",ans);
	return 0;
}
inline void insert(int x,int y){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
inline bool path(int x){//找增广路
	for(edge* e=last[x];e;e=e->prev){
		int y=e->to;
		if(!vis[y]){
			vis[y]=true;
			if(!cb[y]||path(cb[y])){
				//如果y集合中的v元素没有匹配或者是v已经匹配，
				//但是从cy[v]中能够找到一条增广路
				ca[x]=y;
				cb[y]=x;//找到增广路，修改匹配M
				return true;
			}
		}
	}
	return false;
}
inline int maxmatch(){//求最大匹配
	int result=0;
	for(int i=1;i<=na;i++){
		if(!ca[i]){//还没被匹配
			memset(vis,0,sizeof(vis));
			result+=path(i);//以i为起点开始查找增广路，若返回true，匹配数+1
		}
	}
	return result;
}
int haha=MAIN();
int main(){;}
/*
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
Answer:
3
*/