题解 P3980 【[NOI2008]志愿者招募】

· · 题解

题面

惊喜

​ 又一次考试网络流爆零......

​ 这一题一看就是网络流, 但是要怎么构图呢? 考虑到途中的一些因素, 首先, 每一种志愿者控制的区间范围为S_{i}到T_{i}, 所以, 我们要使得每种志愿者只能控制这段区间, 其他的不能够控制, 其次, 每个时间都有一个最小的值, 也就是这条边(我们将时间段看为一条边更加方便)有一个下界, 想到了什么, 上下界网络流, 每条边都要符合上界和下界的约束, 没有学过的可以戳一下.

​ 那么初始的构图也就出来了, 每个时间作为一条边, 那么由i向i + 1连一条边, 容量为INF - lower(i), 费用为0(由于人是控制一段区间的, 他在这段区间中的任意两个点流费用都为0, 可以看做这个人继续做事, 已经付钱了, 你得给我做完事才能走)(lower(i)代表时间i最少需要多少人, 其实这条边容量为INF没有问题, 假装上界为INF + lower(i)就可以了, 反正可以不停地流), 考虑到之前所说, 每个点只能约束自己的一段区间, 有点像循环流, 从S_{i}出发, 流到T_{i}就重新流, 但是这里由于T_{i}被看成了一条边, 所以我们需要在点T_{i} + 1往S_{i}连一条容量为INF, 费用为c的边, 代表当前类i的志愿者控制且只能控制S_{i}到T_{i}这段时间.

​ 最终构图是这样的: 每个点i向i + 1连边, 每个T_{i} + 1向S_{i}连边, 注意在每个点i向i + 1连边时, 由于你是默认这条边流了一个下界的, 你每个点的流量不一定平衡, 记录一下每个点流入和流出的差, 对于一条下界为x的边i -> i + 1, 记delta[i]为点i流入与流出的差, 则delta[i] -= x, delta[i + 1] += x, 连完所有边后, 注意到每个点的delta不一定为0, 对于delta大于或者小于0的情况, 戳上面那个吧, 有详细的介绍, 最后跑一遍无源汇上下界最小费用可行流就可以了, 也就是在构出的有源汇的图中跑一遍最小费用最大流即可.

具体代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define N 2005
#define INF 1e9
using namespace std;

int n, m, S, T, delta[N], head[N], cnt = 1, p[N], vis[N]; 
struct node
{
    int from, to, next;
    long long flow, cost; 
} edge[100005];
long long a[N], d[N]; 

inline int read()
{
    int x = 0, w = 1;
    char c = getchar();
    while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * w;
}

inline void add(int u, int v, long long w, long long cost)
{
    edge[++cnt] = { u, v, head[u], w, cost }; head[u] = cnt;
    edge[++cnt] = { v, u, head[v], 0, -cost }; head[v] = cnt; 
}

bool SPFA(long long &cost)
{
    memset(d, 0x3f, sizeof(d)); memset(a, 0x3f, sizeof(a)); 
    queue<int> q; q.push(S); d[S] = 0; vis[S] = 1; 
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(d[v] > d[u] + edge[i].cost && edge[i].flow > 0)
            {
                d[v] = d[u] + edge[i].cost; a[v] = min(a[u], edge[i].flow);
                p[v] = i; if(!vis[v]) { vis[v] = 1; q.push(v); }
            }
        }
    } 
    if(d[T] == d[0]) return 0;
    cost += (a[T] * d[T]); 
    for(int i = T; i != S; i = edge[p[i]].from)
    {
        edge[p[i]].flow -= a[T]; edge[p[i] ^ 1].flow += a[T]; 
    }
    return 1; 
}

int main()
{
    n = read(); m = read();
    S = n + 2; T = S + 1; 
    for(int i = 1; i <= n; i++) { int x = read(); add(i, i + 1, INF, 0); delta[i] -= x; delta[i + 1] += x; }
    for(int i = 1; i <= m; i++)
    {
        int u = read(), v = read(), c = read();
        add(v + 1, u, INF, c); 
    }
    for(int i = 1; i <= n + 1; i++)
    {
        if(delta[i] < 0) add(i, T, -delta[i], 0);
        if(delta[i] > 0) add(S, i, delta[i], 0); 
    } 
    long long cost = 0;
    while(SPFA(cost));
    printf("%lld\n", cost); 
    return 0;
}