UVALive - 6571 It Can Be Arranged 最大流

时间：2024-03-26 08:35:08

题目链接：

http://acm.hust.edu.cn/vjudge/problem/48415

It Can Be Arranged

Time Limit: 3000MS
#### 问题描述
> Every year, several universities arrange inter-university national programming contests. ACM ICPC
> Dhaka site regional competition is held every year in Dhaka and one or two teams are chosen for ACM
> ICPC World Finals.
> By observing these, MMR (Mission Maker Rahman) has made a plan to open a programming
> school. In that school, N courses are taught. Each course is taught every day (otherwise, programmers
> may forget DP while learning computational geometry!). You will be given the starting time Ai and
> finishing time Bi (inclusive) of each course i (1 ≤ i ≤ N). You will be also given the number of students
> registered for each course, Si (1 ≤ i ≤ N). You can safely assume no student has registered to two
> different courses. MMR wants to hire some rooms of a building, named Sentinel Tower, for running that
> school. Each room of Sentinel Tower has a capacity to hold as much as M students. The programmers
> (students) are very restless and a little bit filthy! As a result, when coursei
> is taken in a class room,
> after the class is finished, it takes cleanij time to clean the room to make it tidy for starting teaching
> coursej immediately just after coursei in the same room.
> Your job is to help MMR to decide the minimum number of rooms need to be hired to run the
> programming school.
#### 输入
> Input starts with an integer T (T ≤ 100) denoting the number of test cases. Each case starts with two
> integers N (1 ≤ N ≤ 100), number of courses and M (1 ≤ M ≤ 10000), capacity of a room. Next N
> lines will contain three integers Ai
> , Bi (0 ≤ Ai ≤ Bi ≤ 10000000) and Si (1 ≤ Si ≤ 10000), starting
> and finishing time of a course. Next N lines will contain the clean time matrix, where the i-th row will
> contain N integers cleanij (1 ≤ i ≤ N, 1 ≤ j ≤ N, 0 ≤ cleanij ≤ 10000000, cleanii = 0).
#### 输出
> For each case, print the test case number, starting from 1, and the answer, minimum number of rooms
> needed to be hired.

样例

sample input

3

1 5

1 60 12

0

4 1

1 100 10

50 130 3

150 200 15

80 170 7

0 2 3 4

5 0 7 8

9 10 0 12

13 14 15 0

2 1

1 10 1

12 20 1

0 2

5 0

sample output

Case 1: 3

Case 2: 22

Case 3: 2

题意

现在需要上n个课程，每个课程：(s,t,p),描述开始时间，结束时间，和上课人数。

现在有若干个最多能容纳m个人的教室，问如何用最少的教室上完所有的课。

题解

如果教室的容量没有要求，那么这将是一个经典的DAG的最少路径覆盖问题。

加了教室容量限制之后，变成了一个带权的最少路径覆盖问题。

我们可以这样建图：首先拆点，把课程i拆成i，i+n，0到i连边，i+n到2*n+1连边，边权为i课程需要的教室数，然后如果课程i上完能够接着上j，那么就连一条边权为INF的边从i到j+n。 然后跑最大流，这样跑出了的值相当于能够共用的教室数，吧总数-最大流就是答案了。

代码

#include<map>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<string>

#include<iostream>

#include<algorithm>

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define M (l+(r-l)/2)

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long LL;

const int maxn=444;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const int mod=1e9+7;

struct Edge {

	int from,to,cap,flow;

	Edge(int f,int t,int c,int fl):from(f),to(t),cap(c),flow(fl) {}

};

struct Dinic {

	int n,m,s,t;

	vector<Edge> egs;

	vector<int> G[maxn];

	bool vis[maxn];

	int d[maxn];

	int cur[maxn];

	void init(int n) {

		this->n=n;

		for(int i=0; i<=n; i++) G[i].clear();

		egs.clear();

	}

	void addEdge(int from,int to,int cap) {

		egs.push_back(Edge(from,to,cap,0));

		egs.push_back(Edge(to,from,0,0));

		m=egs.size();

		G[from].push_back(m-2);

		G[to].push_back(m-1);

	}

	bool BFS() {

		memset(vis,0,sizeof(vis));

		queue<int> Q;

		Q.push(s);

		d[s]=0;

		vis[s]=1;

		while(!Q.empty()) {

			int x=Q.front();

			Q.pop();

			for(int i=0; i<G[x].size(); i++) {

				Edge& e=egs[G[x][i]];

				if(!vis[e.to]&&e.cap>e.flow) {

					vis[e.to]=1;

					d[e.to]=d[x]+1;

					Q.push(e.to);

				}

			}

		}

		return vis[t];

	}

	int DFS(int x,int a) {

		if(x==t||a==0) return a;

		int flow=0,f;

		for(int& i=cur[x]; i<G[x].size(); i++) {

			Edge& e=egs[G[x][i]];

			if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) {

				e.flow+=f;

				egs[G[x][i]^1].flow-=f;

				flow+=f;

				a-=f;

				if(a==0) break;

			}

		}

		return flow;

	}

	int Maxflow(int s,int t) {

		this->s=s;

		this->t=t;

		int flow=0;

		while(BFS()) {

			memset(cur,0,sizeof(cur));

			flow+=DFS(s,INF);

		}

		return flow;

	}

} dinic;

int n,m;

LL si[maxn],ti[maxn],C[maxn][maxn];

int wi[maxn];

void init() {

	dinic.init(2*n+2);

}

int main() {

	int tc,kase=0;

	scanf("%d",&tc);

	while(tc--) {

		scanf("%d%d",&n,&m);

		init();

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

			scanf("%lld%lld%d",&si[i],&ti[i],&wi[i]);

		}

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

			for(int j=1; j<=n; j++) {

				scanf("%lld",&C[i][j]);

			}

		}

		int sum=0;

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

			int cap=wi[i]%m?wi[i]/m+1:wi[i]/m;

			sum+=cap;

			dinic.addEdge(0,i,cap);

			dinic.addEdge(i+n,2*n+1,cap);

		}

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

			for(int j=1; j<=n; j++) {

				if(ti[i]+C[i][j]<si[j]) {

					dinic.addEdge(i,j+n,INF);

				}

			}

		}

		int ans=dinic.Maxflow(0,2*n+1);

		printf("Case %d: %d\n",++kase,sum-ans);

	}

	return 0;

}

相关文章