BZOJ2557: [Poi2011]Programming Contest

题目大意：n个人m个题目，每个题要r分钟完成。比赛有t分钟。给出每个人会做哪些题目，请你安排一个每个人在什么时候做什么题目，使得做出来的题目数最多。在做题数一样多的情况下，罚时尽量小。

首先可以想到费用流做法，即对于每个人在时间限制内建很多条边，费用分别为1.2.3.4.5.....代表他们做了多少题，然后在能做的关系对间连边，每道题再向汇点连边即可

但是这样边的数目最多可达百万，跑费用流是非常虚（不能过）的，所以我们考虑这张图的特殊点

特殊之处就在于这是一个二分图，且只有源点到左边的点的边上有权值，所以我们可以按照这些边权值的顺序来一个一个往里加，然后增广（实际上就是匈牙利算法）

注意假如一个点这次没能找到增广路，那以后也不会找到，就不用再给他匹配一次了，这样时间复杂度上限是O(N^3)的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 510
#define M 250010
using namespace std;
int to[M],nxt[M],pre[N],cnt;
void ae(int ff,int tt)
{
	cnt++;
	to[cnt]=tt;
	nxt[cnt]=pre[ff];
	pre[ff]=cnt;
}
bool pass[N];
int c[N];
bool used[N];
bool find(int x)
{
	int i,j;
	for(i=pre[x];i;i=nxt[i])
	{
		j=to[i];
		if(used[j]) continue;
		used[j]=true;
		if(!c[j]||find(c[j]))
		{
			c[j]=x;
			return true;
		}
	}
	return false;
}
int main()
{
	int n,m,r,tt,T;
	scanf("%d%d%d%d%d",&n,&m,&r,&tt,&T);
	int i,j,x,y;
	while(T--)
	{
		scanf("%d%d",&x,&y);
		ae(x,y);
	}
	int ans1=0,ans2=0;
	for(j=1;j<=tt/r;j++)
	for(i=1;i<=n;i++)
	if(!pass[i])
	{
		memset(used,0,sizeof(used));
		if(find(i)) ans1++,ans2+=j;
		else pass[i]=true;
	}
	printf("%d %lld",ans1,(long long)ans2*r);
}