CodeChef 上一道有趣的网络流题目

这是一道2016年二月CodeChef上的一道题目，叫做Call Center Schedule。

题目大意是这样的：

一个电话公司有 $P$ 个员工，一个星期有 $D$ 天，每天需要工作 $H$ 个小时。每个员工在每个小时只能做参加会议和与客户通话两件事情中的一件，或者不做。

现在要为安排一个和客户通话的时间表，要求满足

• 每个人每天最多花费 $N$ 个小时在参加会议和通话上
• 第 $i$ 个人每周最多花费 $L_i$ 个小时和客户通话
• 每个人每天在 $LT_\text{begin}$ 到 $LT_\text{end}$ 的时间内至少要有 $1$ 小时没有被安排任务
• 对于第 $i$ 天第 $j$ 个小时，恰好有 $R_{i, j}$ 个人可以和客户通话

另外，开会的时间表已经安排完成，如果 $F_{k, i, j}$ 是 $0$ 则表示第 $k$ 个人在第 $i$ 天的第 $j$ 个小时开会，如果是 $1$ 则表示他可以被安排去和客户通话。

时限是 2s，最多 5 组数据，并且 $1 \leq N \leq H \leq 70$, $1 \leq D, P \leq 70$, $1 \leq L_i \leq ND$, $0 \leq R_{i, j} \leq 15$, $F_{k, i, j} \in {0, 1}$, $1 \leq LT_{begin} \leq LT_{end} \leq N$。

这题主要是题目限制条件极其多，但是仔细思考，可以发现这题其实并不是很困难。

我们把人的节点分为三层：

• 第一层对每个人建立一个节点，从源向第 i 个人连接一条容量 L_i 的边。这表示每周的通话时间限制。
• 然后由于每个人每天还有通话时间限制，第二层给每个人建立 D 个节点。上面第 i 个人的节点向现在第 i 个人第 j 天的节点连接一条容量为这个人在今天可以自由安排的小时数（也就是 H 减去今天他开会的小时数）。
• 接下来由于有某段时间有 1 小时不能被安排任务，那么在第三层将第 i 个人第 j 天再加两个节点。一个表示特殊的那段时间，从第 i 个人第 j 天那个节点向这个节点连接一条容量为这段时间可以自由安排小时数减去 1 的边，这样不管如何增广，这段区间都会有至少一个空闲的小时。另一个表示其余时间，就从第 i 个人第 j 天那个节点向这个节点连接容量为这段时间可以自由安排小时数的边。

继续对每个小时建立一个节点，如果某个人在某个小时没有开会，就从第三层对应节点向刚刚的小时节点连接容量为 1 的边。小时节点再向汇连接容量为这个小时应该接待的客户数的边。

之后跑最大流，如果流向汇的边全部都满了，就说明找到了可行方案。

#include <algorithm>
#include <cstring>

const int MaxN = 70, MaxV = 20000, MaxE = 2000000;
int total, S, T;
int P, D, H, N, LTbegin, LTend;
int head[MaxV], next[MaxE], point[MaxE];
int cur[MaxV], cap[MaxE], flag[MaxV], que[MaxV];
int L[MaxN], R[MaxN][MaxN], F[MaxN][MaxN][MaxN];

void add_edge0(int u, int v, int c)
{
	point[++total] = v;
	next[total] = head[u];
	cap[total] = c;
	head[u] = total;
}

void add_edge(int u, int v, int c)
{
	if(c <= 0) return;
	//printf("%d %d %d\n", u, v, c);
	add_edge0(u, v, c);
	add_edge0(v, u, 0);
}

bool bfs()
{
	std::memset(flag, 0, sizeof(flag));
	int qh = 0, qt = 0;
	que[qt++] = T, flag[T] = 1;
	while(qh != qt)
	{
		int u = que[qh++];
		for(int k = head[u]; k; k = next[k])
		{
			int v = point[k];
			if(!flag[v] && cap[k ^ 1])
			{
				flag[v] = flag[u] + 1;
				que[qt++] = v;
			}
		}
	}

	return flag[S];
}

int dfs(int u, int rest)
{
	if(u == T) return rest;
	int used = 0;
	for(int &k = cur[u]; k; k = next[k])
	{
		int g = std::min(rest - used, cap[k]);
		if(g && flag[point[k]] + 1 == flag[u])
		{
			g = dfs(point[k], g);
			cap[k] -= g;
			cap[k ^ 1] += g;
			used += g;
			if(used == rest) break;
		}
	}

	return used;
}

int flow()
{
	int ans = 0;
	while(bfs())
	{
		std::memcpy(cur, head, sizeof(cur));
		ans += dfs(S, ~0u >> 1);
	}

	return ans;
}

int people(int p, int d, int t) 
{
	// people, day, type (lunch, other)
	return P + D * P + 2 * D * p + 2 * d + t + 3;
}

int day(int d, int h) {
	// day, hour
	return (3 * D + 1) * P + d * H + h + 3;
}

bool solve()
{
	total = 1;
	std::memset(head, 0, sizeof(head));

	int sum = 0;

	// input
	std::scanf("%d %d %d %d", &P, &D, &H, &N);

	for(int i = 0; i != P; ++i)
		std::scanf("%d", L + i);

	std::scanf("%d %d", &LTbegin, &LTend);

	for(int i = 0; i != D; ++i)
		for(int j = 0; j != H; ++j)
		{
			std::scanf("%d", R[i] + j);
			sum += R[i][j];
		}

	for(int k = 0; k != P; ++k)
		for(int i = 0; i != D; ++i)
			for(int j = 0; j != H; ++j)
				std::scanf("%d", F[k][i] + j);

	// build
	S = 1, T = 2;
	for(int i = 0; i != D; ++i)
		for(int j = 0; j != H; ++j)
			add_edge(day(i, j), T, R[i][j]);

	for(int k = 0; k != P; ++k)
	{
		int pid = k + 3;
		add_edge(S, pid, L[k]);
		for(int i = 0; i != D; ++i)
		{
			int m[2] = {0, 0};
			for(int j = 0; j != H; ++j)
			{
				int lunch = (LTbegin <= j + 1 && j + 1 <= LTend) ? 0 : 1;
				m[lunch] += 1 - F[k][i][j];
				if(F[k][i][j])
					add_edge(people(k, i, lunch), day(i, j), 1);
			}

			int did = P + D * k + i + 3, LT = LTend - LTbegin + 1;
			if(N < m[0] + m[1] || LT == m[0]) return false;
			add_edge(pid, did, N - m[0] - m[1]);
			add_edge(did, people(k, i, 0), LT - m[0] - 1);
			add_edge(did, people(k, i, 1), H - LT - m[1]);
		}
	}

	return flow() == sum;
}

int main()
{
	std::freopen("schedule.in", "r", stdin);
	std::freopen("schedule.out", "w", stdout);
	int t;
	std::scanf("%d", &t);
	while(t --> 0)
		std::puts(solve() ? "Yes" : "No");
	return 0;
}