HDU 2883 kebab

传送门

有N个顾客，每个顾客需要一些烤串，每个烤串的制作时间不同（一个顾客内是相同的），每个顾客有一个开始时间和截止时间，在小于等于截止时间的时候完成。这个老板可以最多同时烤M串，可以把一个串分为多个不连续的时间段来烤，甚至可以把一个串分为多个部分（根据时间划分）来同时烤（占用多个位置，子串的烧烤时间和分量成正比）。
其实就是有N个任务，每个任务有ni*ti个单位，这些单位随便任意组合（上述那些奇奇怪怪的东西就是说明每个单位都是独立的），一个时间最多完成M个单位，问你能不能在每个任务的规定时间内完成这些任务。

这道题类似HDU 3572，差别在于，那道题限制在每个时间只能完成某个任务的1个单位。建图方法类似，但有不同，这道题我们不用再限制从任务点到时间点的边的容量（直接INF），因为如果我们设成一个不小于min(ni*ti,M)的实际值是没有意义的。另外，这道题的时间的取值上限太大了，不能每个时间都建一个点，巧妙地转化为时间区间（最多2N-1个时间区间），把每个任务的上下限时间塞到set里面，set可以自动去重并从小到大排序，一个接一个组成时间区间，每个时间区间一定是某个或某些个任务的上下限时间的子集。
不用担心在某个时间区间内过来的那些单位不按照每个时间最多M个单位的规定来执行，可以设想它们是有序的。（在一个时间区间内，已确定过来的单位后，怎样处理都是等价的，对外就是一个黑箱，反正处理完了就行。）
另外，通过看样例才能知道，这道题的上下限时间是一个半开半闭区间（这样正好划分子区间），不是全闭区间。

dinic

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <set>
using namespace std;

const int MAX = 2 + 200 + 200 * 2 - 1 + 10;
const int INF = 1e9;

int N, M;
int level[MAX];
int cur[MAX];
int flow;
int cnt;
int S[MAX], E[MAX];

struct Edge
{
	int from, to, flow, cap;
};
vector<Edge> ve;
vector<int> v[MAX];
set<int> interval;

void init()
{
	ve.clear();
	for (int i = 0; i < MAX; i++)
		v[i].clear();
	flow = cnt = 0;
	interval.clear();
}

void addEdge(int from, int to, int weight)
{
	ve.push_back(Edge{ from,to,0,weight });
	ve.push_back(Edge{ to,from,0,0 });
	v[from].push_back(ve.size() - 2);
	v[to].push_back(ve.size() - 1);
}

bool bfs(int dst)
{
	queue<int> q;
	memset(level, -1, sizeof level);
	q.push(0);
	level[0] = 0;
	for (; !q.empty();)
	{
		int x = q.front();
		q.pop();
		for (int i = 0; i < v[x].size(); i++)
		{
			Edge& e = ve[v[x][i]];
			if (level[e.to] < 0 && e.flow < e.cap)
			{
				level[e.to] = level[x] + 1;
				q.push(e.to);
			}
		}
	}
	return level[dst] >= 0;
}

int dfs(int x, int dst, int f)
{
	if (x == dst || f == 0) return f;
	for (int& i = cur[x]; i < v[x].size(); i++)
	{
		Edge& e = ve[v[x][i]];
		int f0;
		if (level[e.to] == level[x] + 1 && (f0 = dfs(e.to, dst, min(f, e.cap - e.flow))))
		{
			e.flow += f0;
			ve[v[x][i] ^ 1].flow -= f0;
			return f0;
		}
	}
	return 0;
}

int main()
{
	for (; ~scanf("%d%d", &N, &M);)
	{
		init();
		int a, b, c, d;
		for (int i = 1; i <= N; i++)
		{
			scanf("%d%d%d%d", &a, &b, &c, &d);
			addEdge(0, i, b*d);
			cnt += b*d;
			interval.insert(a);
			interval.insert(c);
			S[i] = a;
			E[i] = c;
		}
		auto it0 = interval.cbegin();
		auto it = interval.cbegin();
		it++;
		int cnt0 = N + 1;
		for (; it != interval.cend(); it++, it0++)
		{
			addEdge(cnt0++, N + N * 2 - 1 + 1, ((*it) - (*it0))*M);
			for (int i = 1; i <= N; i++)
			{
				if (S[i] <= (*it0) && E[i] >= (*it))
					addEdge(i, cnt0 - 1, INF);
			}
		}
		for (; bfs(N + N * 2 - 1 + 1);)
		{
			memset(cur, 0, sizeof cur);
			int temp;
			for (; temp = dfs(0, N + N * 2 - 1 + 1, INF);)
				flow += temp;
		}
		printf("%s\n", flow == cnt ? "Yes" : "No");
	}

	return 0;
}