【題意】：Alice有n部電影要拍，每部電影必須在每個(gè)星期特定的日子才能拍攝，并且要在限期之內(nèi)拍攝完成。問(wèn)Alice能否拍攝完成所有的電影？

【題解】：比較裸的最大流模型，一開始就想到把每個(gè)星期拆成7個(gè)點(diǎn)代表星期1到星期天，但是覺(jué)得這樣處理點(diǎn)數(shù)太多，看了一下別人的題解，我暈了，全部都是這樣做的。看來(lái)經(jīng)驗(yàn)不足，導(dǎo)致不夠膽下手。說(shuō)下構(gòu)圖，加入一個(gè)源點(diǎn)s，向每部電影連邊，容量為電影要拍的天數(shù)；對(duì)于每部電影，向它能夠拍攝的日子連邊，容量為1，這些日子必須在這部電影的限期之內(nèi)；加入一個(gè)匯點(diǎn)t，每個(gè)日子向t連邊，容量為1，表示一天只能拍攝一部電影。最后判斷一下最大流是否等于所有電影要拍的天數(shù)和即可。

【代碼】：
  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 }