【题意】：Alice有n部电影要拍，每部电影必须在每个星期特定的日子才能拍摄，并且要在限期之内拍摄完成。问Alice能否拍摄完成所有的电影？
【题解】：比较裸的最大流模型，一开始就想到把每个星期拆成7个点代表星期1到星期天，但是觉得这样处理点数太多，看了一下别人的题解，我晕了，全部都是这样做的。看来经验不足，导致不够胆下手。说下构图，加入一个源点s，向每部电影连边，容量为电影要拍的天数；对于每部电影，向它能够拍摄的日子连边，容量为1，这些日子必须在这部电影的限期之内；加入一个汇点t，每个日子向t连边，容量为1，表示一天只能拍摄一部电影。最后判断一下最大流是否等于所有电影要拍的天数和即可。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define maxn 400
6 #define maxm 15000
7 const int inf = 1 << 30;
8 int n, m, s, t;
9 int eh[maxn], low[maxn], pre[maxn], cur[maxn], tot, cnt[maxn], dist[maxn];
10 int film[25][10], week, sum;
11 struct Edge {
12 int u, v, cap, flow, next;
13 }et[maxm];
14
15 void init() {
16 tot = 0;
17 memset(eh, -1, sizeof(eh));
18 }
19
20 void add(int u, int v, int cap, int flow) {
21 Edge e = {u, v, cap, flow, eh[u]};
22 et[tot] = e;
23 eh[u] = tot++;
24 }
25
26 void addedge(int u, int v, int cap) {
27 add(u, v, cap, 0), add(v, u, 0, 0);
28 }
29
30 int isap(int s, int t, int n) {
31 int u, v, now, flow = 0;
32 memset(dist, 0, sizeof(dist));
33 memset(cnt, 0, sizeof(cnt));
34 memset(low, 0, sizeof(low));
35 for(u = 0; u <= n; u++) cur[u] = eh[u];
36 low[s] = inf, cnt[0] = n;
37 u = s;
38 while(dist[s] < n) {
39 for(now = cur[u]; now != -1; now = et[now].next)
40 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1)
41 break;
42 if(now != -1) {
43 cur[u] = pre[v] = now;
44 low[v] = min(low[u], et[now].cap - et[now].flow);
45 u = v;
46 if(u == t) {
47 for(; u != s; u = et[pre[u]].u) {
48 et[pre[u]].flow += low[t];
49 et[pre[u]^1].flow -= low[t];
50 }
51 low[s] = inf, flow += low[t];
52 }
53 } else {
54 if(--cnt[dist[u]] == 0) break;
55 dist[u] = n, cur[u] = eh[u];
56 for(now = eh[u]; now != -1; now = et[now].next)
57 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
58 dist[u] = dist[et[now].v] + 1;
59 cnt[dist[u]]++;
60 if(u != s) u = et[pre[u]].u;
61 }
62 }
63 return flow;
64 }
65
66 void build() {
67 init();
68 s = 0; t = n + week * 7 + 1;
69 for(int i = 1; i <= n; i++) {
70 addedge(s, i, film[i][8]);
71 for(int j = 1; j <= film[i][9]; j++) {
72 for(int k = 1; k <= 7; k++) {
73 if(film[i][k]) addedge(i, n + (j - 1) * 7 + k, 1);
74 }
75 }
76 }
77 for(int i = 1; i <= week; i++)
78 for(int j = 1; j <= 7; j++)
79 addedge(n + (i - 1) * 7 + j, t, 1);
80 }
81
82 int main() {
83 int T;
84 scanf("%d", &T);
85 while(T--) {
86 scanf("%d", &n);
87 week = sum = 0;
88 for(int i = 1; i <= n; i++) {
89 for(int j = 1; j <= 9; j++)
90 scanf("%d", &film[i][j]);
91 week = max(week, film[i][9]);
92 sum += film[i][8];
93 }
94 build();
95 int ans = isap(s, t, t - s + 1);
96 if(ans == sum) printf("Yes\n");
97 else printf("No\n");
98 }
99 return 0;
100 }