记录编号	290386	评测结果	AAWWAEEEEE
题目名称	田忌赛马	最终得分	30
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	0.666 s
提交时间	2016-08-06 13:51:00	内存使用	8.05 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5010;
struct edge{
	int to;
	edge *prev;
	edge():prev(NULL){}
}ee[maxn*200];
void insert(int,int,edge**);
bool path(int,edge**);
int Hungary(edge**);
int ca[maxn],cb[maxn];
bool vis[maxn];
edge *alast[maxn]={NULL},*blast[maxn]={NULL};
int n,a[maxn],b[maxn],len=0,x,y;
int main(){
	freopen("horsea.in","r",stdin);
	freopen("horsea.out","w",stdout);
	scanf("%d",&n);
	for(int j=1;j<=n;j++)scanf("%d",&b[j]);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		if(a[i]>b[j])insert(i,j,alast);
		if(a[i]>=b[j])insert(i,j,blast);
	}
	x=Hungary(alast);
	y=Hungary(blast);
	printf("%d",(x-n+y));
	fclose(stdin);
	fclose(stdout);
	return 0;
}
void insert(int x,int y,edge **last){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
bool path(int x,edge **last){
	int y;
	for(edge *e=last[x];e;e=e->prev){
		y=e->to;
		if(!vis[y]){
			vis[y]=true;
			if(!cb[y]||path(cb[y],last)){
				ca[x]=y;
				cb[y]=x;
				return true;
			}
		}
	}
	return false;
}
int Hungary(edge **last){
	memset(ca,0,sizeof(ca));
	memset(cb,0,sizeof(cb));
	int ans=0;
	for(int i=1;i<=n;i++)if(!ca[i]){
		memset(vis,0,sizeof(vis));
		if(path(i,last))ans++;
	}
	return ans;
}
/*
3
92 83 71
95 87 74
Answer:
200
*/
/*
对每对马，如果田忌的跑得快则连一条边，
然后跑Hungary求二分图最大匹配。
*/