SWERC 2013 B It Can Be Arranged

发表于 更新于 分类于 ， ， 本文字数： 2.4k 阅读时长 ≈ 2 分钟

task

一所编程学院每天将有n门课程。
你将被给定每一门课程的开始和结束时间，以及有多少学生上这门课。当然不会有人愿意一天学两门不同的课。
学校将租用一些房间作为学院的教室，每个房间最多只能坐下M个人。
由于一个房间上完一节课后会被学生们弄得很脏，所以在第i门课结束后，第j门节课在此教室上课之前，他需要用clean(i,j)的时间去清扫这间教室。
为了节省经费，学校想知道最少需要租几间教室，才能满足一天顺利地上完n门课程。

$n<=100$
$m,Si <=10000$
$Ai,Bi,clean(i,j)<=10000000$

solution

由于一间教室可能容不下一节课的所有学生，所以上一节课时我们可能需要多个房间。
发现贪心，动规等策略都没什么办法后，我们可以开始考虑建模。
显然我们可以把所有的可以放在同一间教室上课的课程之间连一条边。
这样我们就构出了一张图，那么我们要怎样在这张图中得出我想要的答案呢？
我们可以运用最大流算法，但是我们要求的不是最大而是最小需要的房间，怎么办呢？
最小，肯定是在总量中减去最大的，所以我们反过来求最大有都少节课可以在同一间教室上课。
对于网络流，首先我们需要一个源点和一个汇点，其次我们还需要将点i拆成i和i+n，防止不合法的两节课连在一起。那么i与源点相连，i+n与汇点相连。
至于边的容量，显然与源点和汇点相连的边就是该课程所需要的房间个数。然后其他边就是oo。
最后将最多需要的房间量减去这个值就好了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <algorithm>
#define M 205
#define N 10005
#define oo 1000000007
using namespace std;
struct kxj{
	int t,nxt,c;
}E[N<<1];
int clean[105][105],A[105],B[105],S[105];
int n,Q[M],dis[M],head[M],tot,cur[M];
bool mark[105];
void Add(int a,int b,int c){
	E[tot]=(kxj){b,head[a],c};head[a]=tot++;
	E[tot]=(kxj){a,head[b],0};head[b]=tot++;
}
bool bfs(){
	for(int i=0;i<=n;i++)dis[i]=-1;
	int L=0,R=0;
	Q[R++]=0;dis[0]=0;
	while(L<R){
		int x=Q[L++];
		for(int i=head[x];~i;i=E[i].nxt){
			int y=E[i].t;
			if(E[i].c&&dis[y]==-1){
				dis[y]=dis[x]+1;
				Q[R++]=y;
			}
		}
	}
	return dis[n]!=-1;
}
int dfs(int x,int flow){
	int res=0;
	if(x==n||flow==0)return flow;
	for(int &i=cur[x];~i;i=E[i].nxt){
		int y=E[i].t;
		if(E[i].c&&dis[y]==dis[x]+1){
			int tmp=dfs(y,min(E[i].c,flow));
			E[i].c-=tmp;
			E[i^1].c+=tmp;
			flow-=tmp;
			res+=tmp;
			if(flow==0)break;
		}
	}
	return res;
}
int Dinic(){
	int ans=0;
	while(bfs()){
		for(int i=0;i<=n;i++)cur[i]=head[i];
		ans+=dfs(0,oo);
	}
	return ans;
}
int main(){
	int T,m,o=0;
	scanf("%d",&T);
	while(T--&&scanf("%d %d",&n,&m)){
		memset(head,-1,sizeof(head));
		memset(mark,0,sizeof(mark));
		tot=0;
		int ans=0;
		for(int i=1;i<=n;i++)scanf("%d %d %d",A+i,B+i,S+i),S[i]=(S[i]-1)/m+1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&clean[i][j]);
		for(int i=1;i<=n;i++){
			ans+=S[i];
			Add(0,i,S[i]);
			for(int j=1;j<=n;j++)
				if(A[j]>B[i]+clean[i][j])Add(i,j+n,oo);
			Add(i+n,n+n+1,S[i]);
		}
		n=n+n+1;
		printf("Case %d: %d\n",++o,ans-Dinic());
	}
	return 0;
}