[NOI2008] 志愿者招募

Description

$\text{Link}$

Solution

网络流解方程。

设 $t_i$ 表示第 $i$ 天的人数，$x_i$ 表示第 $i$ 种员工的数量。我们可以得到如下 $n$ 个不等式：

$\text{E}_i: t_i=\sum_{i\in[s_j,t_j]}x_j\ge a_i$

我们给第 $i$ 行设置辅助变量 $y_i$，表示多选了多少个。显然 $y_i\geq 0$ 。
不等式可以转化为等式：

$\text{E}_i: t_i=y_i+\sum_{i\in [s_j,t_j]}x_j = a_i$

拿到这些等式仍然不好处理。我们需要转化为可以用网络流处理的形式。

增加两个方程，分别为 $\text{E}_0: t_0=0$ 和 $\text{E}_{n+1}: t_{n+1}=0$ 。然后差分，用下面的方程减去上面的方程得到 $n+1$ 个新方程，并且把常数项移到左边（右边均为 $0$）。可以发现，在这 $n+1$ 个方程中有如下性质：

• 每个 $x_i$ 作为正负各出现一次。
• 每个 $y_i$ 作为正负各出现一次。
• 每个等式中有正有负，并且右边是 $0$ 。

事实上，每个等式的形式与网络流中的「流量平衡」很相似。正的变量类似流入的流量，负的变量类似流出的流量。

我们考虑对等式 $i$ 建节点 $i$ ，对于等式中的常数 $x$ ，如果为正，就由源点向该点连容量为 $x$ 的边；否则，就从该点向汇点连容量为 $-x$ 的边。

对于每个变量，我们由变量系数为负的等式向系数为正的等式连容量为该变量取值上限的边（本题中 $x,y$ 均为 $\infin$）。

由于 $x_i$ 每增加一是有代价的，并且我们的目的是最小化代价和。所以我们给每条边加上费用，除了 $-x_i\rightarrow +x_i$ 的边费用是 $c_i$ ，其余的都是 $0$ 。

对上图跑最小费用最大流就可以得到答案了。

或许这也算是一个小 trick ？ 设置辅助变量转为等式那一步很妙，之后的模型转化不是特别难，只是要记清楚适用的条件或者做适当的变化。
以后在题目中可以多多尝试这种方法。

Code

#define oo 1e9
#define debug(...) fprintf(stderr, __VA_ARGS__)
class Input{
private:
    char buf[1000000], *p1, *p2;
public:
    inline char getc(){
        if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
        return p1 == p2 ? EOF : *(p1++);
    }
    template<typename tp>inline Input& operator >> (tp &n){
        n = 0; char c = getc();
        while(!isdigit(c)) c = getc();
        while( isdigit(c)) n = n * 10 + c - 48, c = getc();
        return (*this);
    }
}fin;
using namespace std;
const int N = 1e3 + 233, M = 1e5 + 5;
int n, m, S, T, num = 1;
int a[N], head[N], nt[M], to[M], inq[N], pre[N];
long long cost;
long long val[M], dis[N], cap[M], inc[N];
bool SPFA(void);
void calc(void);
void add(int, int, int, int);
int main(){

    fin >> n >> m;
    S = 0, T = n + 2;
    for(int i = 1; i <= n; ++i)
        fin >> a[i];
    for(int i = 1; i <= n + 1; ++i)
        if(a[i] - a[i - 1] > 0) add(S, i, a[i] - a[i - 1], 0);
        else add(i, T, a[i - 1] - a[i], 0);
    for(int i = 2; i <= n + 1; ++i)
        add(i, i - 1, oo, 0);
    for(int i = 1, a, b, c; i <= m; ++i)
        fin >> a >> b >> c, add(a, b + 1, oo, c);
    while(SPFA())
        calc(); 
    cout << cost << endl;
    return 0;
}
queue<int>q;
bool SPFA(){
    memset(inc, 0, sizeof inc);
    memset(inq, 0, sizeof inq);
    memset(dis, 0x3f, sizeof dis);
    dis[S] = 0, inq[S] = 1, inc[S] = oo; q.push(S);
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(int i = head[x]; i; i = nt[i]){
            int v = to[i]; if(dis[v] <= dis[x] + val[i] or !cap[i]) continue;
            inc[v] = min(cap[i], inc[x]);
            dis[v] = dis[x] + val[i];
            pre[v] = i;
            if(!inq[v]) q.push(v), inq[v] = 1;
        }   
        inq[x] = 0;
    }
    return inc[T] != 0;
}
void calc(){
    int x = T, y;
    while(x != S)
        y = pre[x], cap[y] -= inc[T], cap[y ^ 1] += inc[T], x = to[y ^ 1];
    cost += inc[T] * dis[T];
}
void add(int x, int y, int z, int r){
    ++num, nt[num] = head[x], head[x] = num, to[num] = y, cap[num] = z, val[num] =  r;
    ++num, nt[num] = head[y], head[y] = num, to[num] = x, cap[num] = 0, val[num] = -r;
}