【题意】：给出n个任务和m个机器，每个机器每天只能运行一个任务。对于每个任务，有三个属性p，s，e，表示这个任务至少要在s天后开始运行，至多要在e天前结束运行，并且需要运行p天。问是否存在一种方案使得这n个任务都完成。
【题解】：用网络流来判断是否可行。
把每个任务看成一个点，s到每个任务连边，容量为任务需要运行的天数。
把每天看成一个点，每天向t连边，容量为m，表示一天最多运行m个任务。
每个任务都向s-e天连边，容量为1，表示这个任务可以在这些天运行。
最后判断最大流是否等于所有任务需要运行的天数总和即可。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25
26 const int inf = 1 << 30;
27 #define maxn 1500
28 #define maxm 1000000
29 int n, m, s, t;
30 int eh[maxn], low[maxn], dist[maxn], pre[maxn], cur[maxn], tot, cnt[maxn];
31 struct Edge {
32 int u, v, cap, flow, next;
33 }et[maxm];
34 void init() {
35 tot = 0;
36 memset(eh, -1, sizeof(eh));
37 }
38 void add(int u, int v, int cap, int flow) {
39 Edge e = {u, v, cap, flow, eh[u]};
40 et[tot] = e;
41 eh[u] = tot++;
42 }
43 void addedge(int u, int v, int cap) {
44 add(u, v, cap, 0), add(v, u, 0, 0);
45 }
46 int isap(int s, int t, int n){
47 int u, v, now, flow = 0;
48 memset(dist, 0, sizeof(dist));
49 memset(low, 0, sizeof(low));
50 memset(cnt, 0, sizeof(cnt));
51 for(u = 0 ; u <= n ; u ++) cur[u] = eh[u];
52 low[s] = inf, cnt[0] = n, u = s;
53 while(dist[s] < n) {
54 for(now = cur[u]; now != -1; now = et[now].next)
55 if(et[now].cap - et[now].flow && dist[u] == dist[ v = et[now].v ] + 1 ) break;
56 if(now != -1) {
57 cur[u] = pre[v] = now;
58 low[v] = min(et[now].cap - et[now].flow, low[u]);
59 u = v;
60 if(u == t) {
61 for(; u != s; u = et[pre[u]].u){
62 et[pre[u]].flow += low[t];
63 et[pre[u]^1].flow -= low[t];
64 }
65 flow += low[t]; low[s] = inf;
66 }
67 } else {
68 if(--cnt[dist[u]] == 0) break;
69 dist[u] = n, cur[u] = eh[u];
70 for(now = eh[u]; now != -1; now = et[now].next)
71 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
72 dist[u] = dist[ et[now].v ] + 1;
73 cnt[dist[u]]++;
74 if(u != s) u = et[pre[u]].u;
75 }
76 }
77 return flow;
78 }
79
80 int main() {
81 int T, Case = 1;
82 scanf("%d", &T);
83 while(T--) {
84 scanf("%d%d", &n, &m);
85 init();
86 s = 0, t = n + 500 + 1;
87 int sum = 0;
88 for(int i = 1; i <= n; i++) {
89 int p, start, end;
90 scanf("%d%d%d", &p, &start, &end);
91 sum += p;
92 addedge(s, i, p);
93 for(int j = start; j <= end; j++) {
94 addedge(i, n + j, 1);
95 }
96 }
97 printf("Case %d: ", Case++);
98 for(int i = 1; i <= 500; i++) addedge(i + n, t, m);
99 if(sum == isap(s, t, 2 + n + 500)) puts("Yes");
100 else puts("No");
101 cout << endl;
102 }
103 return 0;
104 }
105