网络流，离散化

题意：

图片说明

分析：

不妨先看看这一题：
hdu3572
可以先做这题
会发现这两题几乎一摸一样
不同之处在于：
1.本题时间跨度大足足有100W,所以如果按照原先的思路我们是要对其离散化的
2.本题中的肉串可以分成k块同时烤制
3.本题中一种肉块有n个

我们要解决这三点。
先从2，3开始：
一块肉可以分为k块同时烤制，最为朴素的思想就是拆点。
但是点数的增多会提高时间复杂度。事实上我们只要对边权k就行了。(肉串到时间的边)
同样，同一种肉串有n个，我们也只要对边权n(肉串到时间的边)
再对start到肉串的边*n就可以了！！
可以画图理解，不是那么好解释。

下面是离散化：
我们时间跨度为100w但是总共最多只有N2个时间节点。
我们不妨对时间快进行离散。
如：肉串1 s=1,t=6
肉串2：s=2,t=4
则这里面有三个连续的时间块：
[1,2),[2,4),[4,6)
这些时间快构成了节点。与肉串相连。
而他们与终点连边的权值也会相应发生变化。
变为该时间块跨度m

如此，我们成功建图，直接使用网络流判断最大流是否等于n*t就可以了

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
const int max_n = 220;
const int max_m = 1100;
const int inf = 2e9;
int n, m;int start, ed;
struct passager { int n, s, t, e; };
passager input[max_n];

struct edge
{
    int to, cap, rev, next;
}E[max_n * max_n * 8];
int head[max_n * 4];
int cnt = 1;
void add(int from, int to, int cap) {
    E[cnt].to = to;
    E[cnt].cap = cap;
    E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];
    head[from] = cnt++;
    E[cnt].to = from;
    E[cnt].cap = 0;
    E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];
    head[to] = cnt++;
}
void init() {
    fill(head, head + max_n * 4, false);
    cnt = 1;
}

int iter[max_n * 4];
int dist[max_n * 4];
bool searchpath(int s, int t) {
    fill(dist, dist + ed + 10, -1);
    queue<int>que;dist[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (dist[e.to] != -1 || e.cap == 0)continue;
            dist[e.to] = dist[u] + 1;
            que.push(e.to);
        }
    }return dist[t] != -1;
}
int matchpath(int u, int t, int f) {
    if (u == t)return f;
    for (int& i = iter[u];i;i = E[i].next) {
        edge& e = E[i];
        if (dist[e.to] <= dist[u] || e.cap == 0)continue;
        int d = matchpath(e.to, t, min(e.cap, f));
        if (d <= 0)continue;
        e.cap -= d;
        E[e.rev].cap += d;
        return d;
    }return false;
}
int dinic(int s, int t) {
    int flow = 0;int f;
    while (searchpath(s, t)) {
        for (int i = 1;i <= ed;i++)iter[i] = head[i];
        while (f = matchpath(s, t, inf))
            flow += f;
    }return flow;
}

int main() {
    ios::sync_with_stdio(0);
    while (cin >> n >> m) {
        vector<int> q;vector<pii> tb;
        init();int sum = 0;
        for (int i = 1;i <= n;i++) {
            cin >> input[i].s >> input[i].n >> input[i].e >> input[i].t;
            q.push_back(input[i].s);q.push_back(input[i].e);
            sum += input[i].t * input[i].n;
        }
        sort(q.begin(), q.end());
        start = n+q.size() + 1, ed = n+q.size() + 2;
        for (int i = 0;i < q.size() - 1;i++) {
            tb.push_back({ q[i],q[i + 1] });
            add(i + 1 + n, ed, m * (q[i + 1] - q[i]));
        }
        for (int i = 1;i <= n;i++) {
            int left = lower_bound(q.begin(), q.end(), input[i].s) - q.begin();
            int right = lower_bound(q.begin(), q.end(), input[i].e) - q.begin();
            add(start, i, input[i].t * input[i].n);
            for (int j = left; j < right;j++)
                add(i, j + 1 + n, (tb[j].second - tb[j].first) * input[i].t * input[i].n);
        }int res = dinic(start, ed);
        if (sum == res)cout << "Yes\n";
        else cout << "No\n";
    }
}

kebab HDU - 2883

网络流，离散化

题意：

分析：

代码如下：