POI2011 PRO-Programming Contest

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Thu Nov 15 20:24:52 CST 2018

In Category: NoCategory

Description：

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

$1\leqslant n\leqslant 500$

Solution：

比较显然的费用流，把从源点到每个人的边拆成 $\min(m,\lfloor t/r\rfloor)$ 条权值不同的边然后跑费用流，大概就是：


for(int i = 1;i <= n;++i)

	for(int j = 1;j <= min(m,T / R);++j)

		add(s,i,1,R * j);

for(int i = 1;i <= m;++i)

	add(i + n,t,1,0);

for(int i = 1;i <= q;++i)

{

	scanf("%d%d",&a,&b);

	add(a,b + n,1,0);

}

但是这样会 $TLE$ ，题解的做法是用匈牙利，即先在外层枚举时间，然后每一层枚举所有点跑匈牙利，最后把答案累加，感觉根本想不到。

复杂度 $O(n^3)$ 。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,R,T,q;

#define MAXN 510

int s,t;

struct edge

{

	int to,nxt;

}e[MAXN * MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int match[MAXN];

bool v[MAXN];

bool kil[MAXN];

bool find(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!v[e[i].to])

		{

			v[e[i].to] = true;

			if(match[e[i].to] == -1 || find(match[e[i].to]))

			{

				match[e[i].to] = k;

				return true;

			}

		}

	}

	return false;

}

int cnt[MAXN];

int sum = 0,ans = 0;

int main()

{

	scanf("%d%d%d%d%d",&n,&m,&R,&T,&q);

	int a,b;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	memset(match,-1,sizeof(match));

	for(int k = 1;k <= min(m,T / R);++k)

	{

		for(int i = 1;i <= n;++i)

		{

			if(kil[i])continue;

			if(find(i))

			{

				memset(v,false,sizeof(v));

				++sum;

				ans += k * R;

			}

			else

			{

				kil[i] = true;

			}

		}

	}

	cout << sum << " " << ans << endl;

	for(int i = 1;i <= m;++i)

	{

		if(match[i] == -1)continue;

		printf("%d %d %d\n",match[i],i,cnt[match[i]] * R);

		++cnt[match[i]];

	}

	return 0;

}

In tag: 图论-匈牙利算法

wjh15101051