网络流复习计划第四题，前几天在复习全国公认挂科率最高的数电，所以一直没做题。
扯一个，数电最后没复习好正打算放弃的时候被老友傻炮拉了一把。应该可以过。
题意：
给你很多任务，每个任务都需要一台机器花费给定的时间才能完成，并且限定了每个任务的完成时间区间( 比如说 [a,b] 在第a天开始，在第b天之前完成，包括b)，一台机器一天只能执行一个任务，有多台机器。问你是否能全部完成任务。
思路：
先歪一个……一开始我看到这题想了一下是想贪心做的，结果在写的过程中就自己 否定–更改 了好几次，结果还是没写出来。
实际上这道题是网络流建图的一道经典题，我们让每一个任务作为流量源点，将每个流量源点与其任务时间区间的每个数建边，流量为1，表示你可以在这个区间内其中任意一天使用一台机器，而每台机器将其作为汇点汇入一个超级汇点即可。
他的数据范围最大都只有500，因为要新建流量源点，所以所有节点数量不超过1000。我觉得复杂度还可以啊，但是discuss里面一堆人都说卡时间，过不去……感觉很奇怪，我是1A的，263s，还没有特意去记录点数，懒得优化……
AC code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int n, m, st, en;
int dis[maxn][maxn];
int flow[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
bool bfs()
{
memset(level, -1, sizeof level);
que[0] = st;
level[st] = 0;
int l = 0, r = 1, u;
while (l < r) {
u = que[l++];
for (int i = 0; i <= 1001; i++)
if (flow[u][i] && level[i] == -1) {
level[i] = level[u] + 1;
que[r++] = i;
}
}
return level[en] != -1;
}
int dfs(int u, int low)
{
int cflow;
if (u == en)
return low;
for (int& i = cur[u]; i <= 1001; i++) {
if (flow[u][i] > 0 && level[i] == level[u] + 1
&& (cflow = dfs(i, min(low, flow[u][i])))) {
flow[u][i] -= cflow;
flow[i][u] += cflow;
return cflow;
}
}
return 0;
}
int dinic()
{
st = 0, en = 1001;
int ans = 0, cflow;
while (bfs()) {
memset(cur, 0, sizeof cur);
while ((cflow = dfs(st, inf)))
ans += cflow;
}
return ans;
}
int main()
{
int T, s, e, len;
scanf("%d", &T);
for (int cas = 1; cas <= T; cas++) {
scanf("%d %d", &m, &n);
memset(flow, 0, sizeof flow);
int sum = 0;
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &len, &s, &e);
sum += len;
flow[0][500 + i] = len;
for (int j = s; j <= e; j++)
flow[500 + i][j] = 1;
}
for (int i = 1; i <= 500; i++)
flow[i][1001] = n;
printf("Case %d: %s\n\n", cas,dinic()==sum?"Yes":"No");
}
return 0;
}