poj 1698 Alice's Chance EK 最大流

缘起

日常浪费生命~ poj 1698 Alice’s Chance

分析

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
题目大意：爱丽丝要拍电影，有n部电影，规定爱丽丝每部电影在每个礼拜只有固定的几天可以拍电影，
只可以拍前面w个礼拜，并且这部电影要拍d天,问爱丽丝能不能拍完所有的电影
而且每天只能从事一部电影的拍摄

【输入】
多样例. 每个样例开始于N.1 <= N <= 20, 然后n行每行9个数字, 每行刻画了一部电影
形如F1 F2 F3 F4 F5 F6 F7 D W
 Fi (1 <= i <= 7) 是 1 或者 0, 1表示星期Fi可以拍, 0表示星期Fi不能拍. D和W如上.
 1 <= D <= 50
 1 <= W <= 50

【输出】
对每个样例输出Yes或者No

【样例输入】
2
2
0 1 0 1 0 1 0 9 3
0 1 1 1 0 0 0 6 4
2
0 1 0 1 0 1 0 9 4
0 1 1 1 0 0 0 6 2

【样例输出】
Yes
No

【限制】
1s

最大流的题目知道怎么建图就好简单（毕竟跑最大流的代码已经只是一个封装好的工具了）.

本题建图的方式比较裸——一类点是电影，有n个. 另一类点是天数. 建一个炒鸡源，建一个炒鸡汇. 炒鸡源到各个电影的弧的容量就是电影需要拍摄的天数. 而各个天数到炒鸡汇的弧的容量就是1, 表示这一天只能进行一部电影的拍摄工作. 中间的电影到天数的弧的容量是1, 表示这一天只能消耗掉一部电影的一天的工时. 然后跑EK算法即可

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
//#define LOCAL

const int maxn = 25, inf = 0x3f3f3f3f;
int n,maxw, a[maxn][15], head[375], cnt,s,t,sum, pre[375], flow[375]; // maxw是最大的周数,s是炒鸡源, t是炒鸡汇,sum是总共需要投入的总天数

struct Arc
{
	int from,to,nxt,cap;
}g[375*375];

void addArc(int from, int to, int cap)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from], g[cnt].cap = cap;
	head[from] = cnt++;
	g[cnt].from = to, g[cnt].to = from, g[cnt].nxt = head[to], g[cnt].cap = 0;
	head[to] = cnt++;
}

void build()
{
	t = maxw*7+n+1; // s是炒鸡源,t是炒鸡汇, 一共7*maxw天,n部电影需要拍摄, 所以除去炒鸡源和炒鸡汇之外, 有maxw*7+n个点
	for (int i = 1; i<=n; i++)
	{
		addArc(0, i, a[i][8]);
	}
	for (int i = n+1; i<t; i++)
	{
		addArc(i, t, 1);
	}
	for (int i = 1; i<=n; i++)
	{
		for (int j = 1; j<=7; j++)
		{
			if (a[i][j]) // 第i部电影可以在每周j进行拍摄, 则i和第一周的星期j,...,第a[i][9]周的星期j连容量为1的弧
			{
				for (int k = 1; k<=a[i][9]; k++)
				{
					addArc(i, n+(k-1)*7+j, 1);
				}
			}
		}
	}
}

void updata(int s, int t, int d)
{
	int h;
	while(t!=s)
	{
		h = pre[t];
		g[h].cap-=d;
		g[h^1].cap+=d;
		t = g[h].from;
	}
}

int bfs(int s, int t)
{
	queue<int> q;
	memset(pre, -1, sizeof(pre));
	flow[s] = inf;
	q.push(s);
	while(!q.empty())
	{
		int front = q.front();
		q.pop();
		if (front==t)
		{
			updata(s,t,flow[t]);
			return flow[t];
		}
		for (int h = head[front],to; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			if (!~pre[to] && g[h].cap>0)
			{
				pre[to] = h;
				flow[to] = min(flow[front], g[h].cap);
				q.push(to);
			}
		}
	}
	return 0;
}

int ek(int s, int t)
{
	int ans = 0;
	while(1)
	{
		int d = bfs(s,t);
		if (!d)
		{
			return ans;
		}
		ans+=d;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		memset(head, -1, sizeof(head));
		maxw = sum = cnt =0;
		scanf("%d", &n);
		for (int i = 1; i<=n ;i++)
		{
			for (int j = 1; j<=7; j++)
			{
				scanf("%d", a[i]+j);
			}
			scanf("%d%d", a[i]+8, a[i]+9);
			maxw = max(maxw, a[i][9]);
			sum+=a[i][8];
		}
		build(); // 建图
		ek(0,t)==sum?puts("Yes"):puts("No");
	}
	return 0;
}

ac情况

Status Accepted
Time 141ms
Memory 776kB
Length 2191
Lang G++
Submitted 2019-09-27 13:45:17
Shared
RemoteRunId 20903606