[Noip2011] sightseeing bus

Title Description

A charming little town $D_i DiMinute. At any time, the bus can only go forward or wait at the scenic spot.$

Joint ownership $inTiT_i TiMinutes to attractionsAiA_i Ai，I hope to travel to the scenic spots.Bi(Ai<Bi)B_i (A_i<B_i)Bi(Ai<Bi)。In order for all passengers to reach their destination smoothly, the bus must wait at each stop for all passengers who need to leave the site to get on the bus before departing for the next attraction.$

Suppose passengers do not need time to get on or off. The travel time of a passenger is equal to the time when he arrives at his destination minus his arrival time. Passengers complain about the long journey because there is only one sightseeing bus and sometimes they have to stop to wait for other passengers. So smart drivers. $D_i-1Di−1 。For the sameDiD_iDi The accelerator can be reused, but it must be guaranteed after use.Di≥0D_i \ge 0Di≥0 。$

that

Input output format

Input format:

The first

The first $D_i Di。$

The first $3IntegersTi,Ai,BiT_i, A_i, B_iTi,Ai,Bi，Each two integers are separated by a space. The firsti+2 i+2i+2 Line representationiii The number of passengers arriving at the starting spot, the number of scenic spots and the number of scenic spots that arrive.$

Output format:

An integer representing the minimum total travel time.

Examples of input and output

Input sample #1: copy

Output sample #1: copy

Explain

【Examples of input and output samples

Yes $D2D_2D2 Use222 An accelerator from222 Number scenic spot to333 Number of attractions changed to222 Minute.$

The bus is in the first place.

The first

Total time

【Data range]

about $10%10\%10% Data,k=0k=0k=0 ；$

about $20%20\% 20%Data,k=1k=1k=1 ；$

about $40%40\%40% Data,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；$

about $60%60\% 60%Data,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；$

about $100%100\%100%Data,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。$

noip2011Improving group Day2 third questions

The greedy way of thinking is to choose the path with the largest number of people, and then if the arrival time of a point is less than the time of the last person to come up at that point, it is no longer necessary.

There is a cost flow algorithm in the solution, which is quite novel.

First, establish three points: $\large S$, $\large S’$, $\large T$.

Then divide each point into two points $\large i$, $\large i’$.

The connection $\large S – S’$, the capacity is k, the cost is 0, representing the total number of restrictions is K.

Let’s set $ large MX [i]$to indicate the maximum departure time for people starting from point I, $ large Tim [i]$to indicate the time from point I, and $ large down [i]$to indicate the number of people getting off at point I.

The edge is $\large I – i’$, the capacity is $\large max (tim[i] – mx[i], 0) $, the cost is 0.

Because if the previous acceleration exceeds $ large Tim [i] MX [i]$, it will not affect the latter, so simply limit the maximum flow of the previous point & lt; = this value.

$\large I’+ I + 1$, capacity is INF, the cost is $\large -down[i+1]$.

With the edge $ large S’i’$, the capacity is $ large D [i]$, the cost is zero, and the allocation accelerator guarantees that the last $ large D [i]$is positive.

The connection is $\large I – T$, the capacity is INF, the cost is 0..

Then write the cost flow.

The train of thought is ingenious and worth learning.

#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\n", ans);
    return 0;
}

Title Description

Input output format

Examples of input and output

Explain

Leave a Reply Cancel reply