链接:点击打开链接
题意：有M个机器(代表一天可以同时干M天的工作)，有N个任务。每个任务必须在Si或者以后开始做，在Ei或者之前完成，完成每个任务必须处理Pi个时间单位，且每台机器每个单位时刻只能进行一个任务,问最后是否可以完成这N个任务
分析:
把每个任务看成一个点，s到每个任务连边，容量为任务需要运行的天数。
把每天看成一个点，每天向t连边，容量为m，表示一天最多运行m个任务。
每个任务都向s-e天连边，容量为1，表示这个任务可以在这些天运行。
最后判断最大流是否等于所有任务需要运行的天数总和即可。
收获：用的是前向星建的图,在寻找出一条增广路径后,反向边的容量就要+flow,但是前向星迷惑了我好久,导致我无法理解方向相反的两条边为什么边的编号差值是1。还有一点就是,多路增广时候,如果从当前点已经无法再找到增广路径了,那么直接可以把路给堵死,使得下次再次dfs到此点的时候不会再度进行同样的搜索，大大地节约了时间，也算是一个强有力的剪枝！最后这个题的建图小技巧值得学习！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1100;
struct edge
{int v, w, next;
}cap[1100000];
int head[maxn], cnt, maxflow;
int dis[maxn];
int q[100550];
int n, m;
//queue<int> q;
void add(int u, int v, int w)
{cap[cnt].v = v;cap[cnt].w = w;cap[cnt].next = head[u];head[u] = cnt++;cap[cnt].v = u;cap[cnt].w = 0;cap[cnt].next = head[v];head[v] = cnt++;
}int bfs(int s, int t)
{int u, v;memset(dis, -1, sizeof(dis));dis[0] = 0;int fir = -1, tail = 0;q[0] = s;while(fir < tail){u = q[++fir];for(int i = head[u]; i != -1; i = cap[i].next){v = cap[i].v;if(dis[v] == -1 && cap[i].w){dis[v] = dis[u] + 1;q[++tail] = v;}}}if(dis[t] > 0)return 1;elsereturn 0;
}/*
int bfs(int s, int t)
{int u, v;memset(dis, -1, sizeof(dis));dis[s] = 0;while(!q.empty())q.pop();q.push(s);while(!q.empty()){u = q.front();q.pop();for(int i = head[u]; i != -1; i = cap[i].next){v = cap[i].v;if(dis[v] == -1 && cap[i].w){dis[v] = dis[u] + 1;q.push(v);}}}if(dis[t] > 0)return 1;return 0;
}
*/int dinic(int s, int t, int low)
{if(s == t)return low;int v, flow, sum = 0;for(int i = head[s]; i != -1; i = cap[i].next){v = cap[i].v;if(dis[v] == dis[s] + 1 && cap[i].w && (flow = dinic(v, t, min(low, cap[i].w)))){cap[i].w -= flow;cap[i^1].w += flow;//反向边的容量+flow,虽然建图用的是前向星,但是方向相反的两条边的编号都是只差1，这点当时被前向星迷惑了好久没想通sum += flow;low -= flow;if(!low)break;}}if(sum)return sum;dis[s] = -1;//如果沿着这个点找不到增广路径，那么直接把路给堵死，下次不会再进入，这句话不加直接就会Treturn 0;
}
int main()
{int T, p, s, e, tol;scanf("%d", &T);for(int kase = 1; kase <= T; kase++){tol = maxflow = cnt = 0;memset(head, -1, sizeof(head));scanf("%d%d", &m, &n);for(int i = 1; i <= m; i++){scanf("%d%d%d", &p, &s, &e);for(int j = s; j <= e; j++)add(j, 500+i, 1);//每件任务和工作期限的区间建立容量为1的边add(500+i, 1001, p);//该任务和超级汇点建立容量为任务所需天数的边tol += p;}for(int i = 1; i <= 500; i++)//超级源点和每台机器建立容量为机器数量的边add(0, i, n);while(bfs(0, 1001)){int flow;while(flow = dinic(0, 1001, INF))maxflow += flow;}printf("Case %d: ", kase);if(tol == maxflow)printf("Yes\n");elseprintf("No\n");puts("");}return 0;
}