[Noip2011] 观光公交

题目描述

风景迷人的小城 $D_i Di分钟。任意时刻，公交车只能往前开，或在景点处等待。$

设共有 $i位游客在TiT_i Ti分钟来到景点 AiA_i Ai，希望乘车前往景点Bi(Ai<Bi)B_i (A_i<B_i)Bi(Ai<Bi)。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。$

假设乘客上下车不需要时间。一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 $D_i-1Di−1 。对于同一个DiD_iDi 可以重复使用加速器，但是必须保证使用后Di≥0D_i ge 0Di≥0 。$

那么

输入输出格式

输入格式：

第

第 $D_i Di。$

第 $Ti,Ai,BiT_i, A_i, B_iTi,Ai,Bi，每两个整数之间用一个空格隔开。第i+2 i+2i+2 行表示第iii 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。$

输出格式：

一个整数，表示最小的总旅行时间。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

【输入输出样例说明】

对 $D2D_2D2 使用222 个加速器，从222 号景点到 333 号景点时间变为 222 分钟。$

公交车在第

第

总时间

【数据范围】

对于 $10%10\%10% 的数据，k=0k=0k=0 ；$

对于 $20%20\% 20%的数据，k=1k=1k=1 ；$

对于 $40%40\%40% 的数据，2≤n≤50,1≤m≤1,000,0≤k≤20,0≤Di≤10,0≤Ti≤5002 ≤ n ≤ 50,1 ≤ m ≤ 1,000,0 ≤ k ≤ 20,0 ≤ D_i ≤ 10,0 ≤ T_i ≤ 5002≤n≤50,1≤m≤1,000,0≤k≤20,0≤Di≤10,0≤Ti≤500；$

对于 $60%60\% 60%的数据，1≤n≤100,1≤m≤1,000,0≤k≤100,0≤Di≤100,0≤Ti≤10,0001 ≤ n ≤ 100,1 ≤ m ≤ 1,000,0 ≤ k ≤ 100,0 ≤ D_i ≤ 100,0 ≤T_i≤ 10,0001≤n≤100,1≤m≤1,000,0≤k≤100,0≤Di≤100,0≤Ti≤10,000；$

对于 $100%100\%100%的数据，1≤n≤1,000,1≤m≤10,000,0≤k≤100,000,0≤Di≤1000≤Ti≤100,0001 ≤ n ≤ 1,000,1 ≤ m ≤ 10,000 ,0 ≤ k ≤ 100,000,0 ≤ D_i ≤ 100 0 ≤T_i ≤ 100,0001≤n≤1,000,1≤m≤10,000,0≤k≤100,000,0≤Di≤1000≤Ti≤100,000。$

noip2011提高组day2第3题

贪心思路很好想，肯定是要选择经过人数最多的路径，然后如果一个点的到达时间小于这个点最后一个上来的人的时间，就不用再这条路径。

题解中有一个费用流的算法，很新奇。

首先建立$large S$, $large S'$, $large T$三个点。

然后把每个点拆成两个点$large i$, $large i'$。

连边$large S - S'$,容量为k，费用为0，代表限制总个数为k。

我们设$large mx[i]$表示从i点出发的人的出发时间最大值，$large tim[i]$表示车到i点的时间,$large down[i]$表示在i点下车的人数。

连边$large i - i'$，容量为$large max(tim[i] - mx[i], 0)$，费用为0.

因为如果前面的加速超过$large tim[i] - mx[i]$，也不会对后面产生影响，所以干脆限制前面的点的最大流<=这个值。

连边$large i' - i + 1$，容量为INF，费用为$large -down[i+1]$.

连边$large S' - i'$，容量为$large D[i]$，费用为0，分配加速器，保证最后的$large D[i]$都是正数。

连边$large i - T$，容量为INF，费用为0.

然后就写费用流就行了。

思路很巧，值得学习。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define reg register
inline int read() {
    int res = 0;char ch = getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return res;
}
#define N 1005
#define M 10005
int n, m, k;
int ans;
int D[N];
int tim[N];//when the bus arrive
int mx[N];//the last passenger arrive time 
int from[M], got[M], beg[M];//from where, to where
int down[N];//how many passengers get off

struct edge {
    int nxt, to, val, flow;
}ed[N*2*2*2];
int head[N*2], cnt = 1;
inline void add(int x, int y, int z, int c)
{
    ed[++cnt] = (edge){head[x], y, c, z};
    head[x] = cnt;
    ed[++cnt] = (edge){head[y], x, -c, 0};
    head[y] = cnt;
}

int dis[N*2];
bool ex[N*2];
int pre[N*2], incf[N*2];
int S, T, S1;

inline bool spfa()
{
    memset(dis, 0x3f, sizeof dis);
    memset(ex, 0, sizeof ex);
    queue <int> q;
    q.push(S);
    dis[S] = 0;
    incf[S] = 0x3f3f3f3f;
    while(!q.empty())
    {
        int x = q.front();q.pop();
        ex[x] = 0;
        for (reg int i = head[x] ; i ; i = ed[i].nxt)
        {
            if (!ed[i].flow) continue;
            int to = ed[i].to;
            if (dis[to] > dis[x] + ed[i].val) {
                dis[to] = dis[x] + ed[i].val;
                pre[to] = i;
                incf[to] = min(incf[x], ed[i].flow);
                if (!ex[to]) ex[to] = 1, q.push(to);
            }
        }
    }
    return dis[T] != 0x3f3f3f3f;
}

inline void update()
{
    int x = T;
    while(x != S)
    {
        int i = pre[x];
        ed[i].flow -= incf[T];
        ed[i^1].flow += incf[T];
        x = ed[i^1].to;
    }
    ans += dis[T] * incf[T];
}

int main()
{
    n = read(), m = read(), k = read();
    for (reg int i = 1 ; i < n ; i ++) D[i] = read();
    for (reg int i = 1 ; i <= m ; i ++) 
    {
        int x = read(), y = read(), z = read();
        mx[y] = max(mx[y], x);
        beg[i] = x, from[i] = y, got[i] = z;
        down[z]++;
    }
    for (reg int i = 1 ; i <= n ; i ++)
        tim[i] = max(tim[i-1], mx[i-1]) + D[i-1];
    for (reg int i = 1 ; i <= m ; i ++) ans += tim[got[i]] - beg[i];
    S = 2 * n + 1, S1 = 2 * n + 2, T = 2 * n + 3;
    add(S, S1, k, 0);
    for (reg int i = 1 ; i < n ; i ++)
    {
        add(i, i + n, max(tim[i] - mx[i], 0), 0);
        add(S1, i + n, D[i], 0);
        add(i + n, i + 1, 0x3f3f3f3f, -down[i+1]);
        add(i + 1, T, 0x3f3f3f3f, 0);
    };
    while(spfa()) update();
    printf("%d
", ans);
    return 0;
}