题意：现在有n个人要烤肉，有m个烤肉架，然后给出每个人的烤肉开始时间si，结束时间ei，以及要烤肉的串数num，还有拷一串的时间ti，然后问你能不能满足所有人的要求。
为3572的进阶题
每个人为一个任务 每个任务的需求量为 需求的肉串数量 ni * 每个肉串烤的时间 ti
3572 任务点到时间点的边为1 是因为一次只能一台机器做一个任务
而这题的话 可以多台机器一起加工一个任务
本来这题可以用3575完全一样的方法来做 但是时间点 s e 属于1到1000000
肯定不能把时间点划分为点
所以要将时间段划分为点 ：
先是超级源点到每一个客人连 ni*ti
再将所有时间点升序 一共j个 所以就有j-1个时间段
如果排序后的时间段被任务的时间段包含 那么连一条inf的线 inf对答案不影响 因为源点到任务点的连线和时间段到汇点的连线会限制好流量
最后 每个时间段对超级汇点连一条 （time[j+1]-time[j]) * m的连线 表示该时间段的最大工作量 3575为1*m
这两题非常经典 值得学习
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = ;
# define inf 0x3f3f3f3f
int p[N],s[N],e[N],v,c,m; struct Edge {
int from, to, cap, flow;
}; bool operator < (const Edge& a, const Edge& b) {
return a.from < b.from || (a.from == b.from && a.to < b.to);
} struct Dinic {
int s,t;
vector<Edge> edges; // 边数的两倍
vector<int> G[N]; // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[N]; // BFS使用
int d[N]; // 从起点到i的距离
int cur[N]; // 当前弧指针 void init(int n) {
for(int i = ; i <=n; i++) G[i].clear();
edges.clear();
} void AddEdge(int from, int to, int cap) {
edges.push_back((Edge){from, to, cap, });
edges.push_back((Edge){to, from, , });
m = edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
} bool BFS() {
memset(vis, , sizeof(vis));
queue<int> q;
q.push(s);
vis[s] = ;
d[s] = ;
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i = ; i < G[x].size(); i++)
{
Edge& e = edges[G[x][i]];
if(!vis[e.to] && e.cap > e.flow)
{
vis[e.to] = ;
d[e.to] = d[x] + ;
q.push(e.to);
}
}
}
return vis[t];
} int DFS(int x, int a) {
if(x == t || a == ) return a;
int flow = , f;
for(int& i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if(d[x] + == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > ) {
e.flow += f;
edges[G[x][i]^].flow -= f;
flow += f;
a -= f;
if(a == ) break;
}
}
return flow;
} int Maxflow(int s, int t) {
this->s = s; this->t = t;
int flow = ;
while(BFS()) {
memset(cur, , sizeof(cur));
flow += DFS(s, INF);
}
return flow;
}
}g; vector<int> time;
struct node
{
int si,num,ei,ti; }a[N];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int cnt=;
int s=,t=*n+,i,j;
for(i=;i<=n;i++)
{
scanf("%d%d%d%d",&a[i].si,&a[i].num,&a[i].ei,&a[i].ti);
time.push_back(a[i].si);
time.push_back(a[i].ei);
int tmp = a[i].num*a[i].ti;
cnt+=tmp;
g.AddEdge(s,i,tmp);
}
sort(time.begin(),time.end());
for(i=;i<=n;i++)
{
for(j=;j<(time.size()-);j++)
{
if(a[i].si<=time[j] && a[i].ei>=time[j+])
g.AddEdge(i,n+j+,inf); }
}
for(i=;i<(time.size()-);i++)
g.AddEdge(n+i+,t,(time[i+]-time[i])*m);
int ans=g.Maxflow(s,t); if(ans==cnt)
printf("Yes\n");
else
printf("No\n"); g.init(t);
time.clear();
}
return ;
}