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

Luogu

分析

这是一个线性规划做法。下面举的栗子为样例。
设 $X_i$ 为第 $i$ 类志愿者的招募数，$P_i$ 为第 $i$ 天招募志愿者的数量，那么可以列出一些不等式
$$ \begin{cases} P_1=X_1\geq 2\\ P_2=X_1+X_2\geq 3\\ P_3=X_3\geq 4 \end{cases} $$
设 $Y_i$ 为第 $i$ 天多招募的数量，那么可以把不等式化为等式
$$ \begin{cases} P_1=X_1-Y_1=2\\ P_2=X_1+X_2-Y_2=3\\ P_3=X_3-Y_3=4 \end{cases} $$
令 $P_0=0,P_4=0$，上下相邻两项相减得
$$ \begin{cases} P_1-P_0=X_1-Y_1=2\\ P_2-P_1=X_2+Y_1-Y_2=1\\ P_3-P_2=-X_1-X_2+X_3+Y_2-Y_3=1\\ P_4-P_3=-X_3+Y_3=-4 \end{cases} $$
注意到每个变量恰出现 $2$ 次且系数一正一负。
我们可以把每个等式看做一个点，正数代表流入，负数代表流出，那么等式相当于流量平衡。
因此我们得到了这样的建图方法：

• 如果 $P_i-P_{i-1}>0$，从源点向 $i$ 连容量为 $P_i-P_{i-1}$、费用为 $0$ 的边，否则从 $i$ 向汇点连容量为 $P_{i-1}-P_i$、费用为 $0$ 的边，表示等式中的常数项。
• 从 $i+1$ 向 $i$ 连容量为 $+\infty$、费用为 $0$ 的边，表示 $Y_i$。
• 对于每类志愿者，从 $s_i$ 向 $t_i+1$ 连容量为 $+\infty$、费用为 $c_i$ 的边，表示 $X_i$。

这样子跑最大流，得到每条边的流量作为对应变量的值，可以得到一组满足不等式的解。而我们希望 $\sum X_i\times w_i$ 最小即整张图的总费用最小，因此求出最小费用最大流即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

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;
}

const int N=1000+10,M=20000+10;
const int inf=0x3f3f3f3f;

int n,m,s,t,p[N];

struct edge { int v,w,c,nxt; } e[M<<1];
int head[N];
inline void addEdge(int u,int v,int w,int c) {
    static int cnt=1;
    e[++cnt]=(edge){v,w,c,head[u]},head[u]=cnt;
    e[++cnt]=(edge){u,0,-c,head[v]},head[v]=cnt;
}

int dis[N],inq[N],lst[N];
inline int spfa() {
    memset(dis,0x3f,sizeof(dis)),memset(lst,0,sizeof(lst));
    queue<int> Q; Q.push(s); dis[s]=0,inq[s]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,c=e[i].c;
            if (e[i].w&&dis[u]+c<dis[v]) {
                dis[v]=dis[u]+c,lst[v]=i;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return lst[t]!=0;
}

int main() {
    n=read(),m=read(),s=0,t=n+2;
    for (re int i=1;i<=n;++i) p[i]=read();
    for (re int i=1;i<=n+1;++i) {
        if (p[i]-p[i-1]>0) addEdge(s,i,p[i]-p[i-1],0);
        else addEdge(i,t,p[i-1]-p[i],0);
    }
    for (re int i=1;i<=n;++i) addEdge(i+1,i,inf,0);
    for (re int i=1;i<=m;++i) {
        int l=read(),r=read(),c=read();
        addEdge(l,r+1,inf,c);
    }
    int ans=0;
    while (spfa()) {
        int f=inf;
        for (re int i=lst[t];i;i=lst[e[i^1].v]) f=min(f,e[i].w);
        for (re int i=lst[t];i;i=lst[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        ans+=dis[t]*f;
    }
    printf("%d\n",ans);
    return 0;
}