[NOI2008] 志愿者招募 （费用流）

[NOI2008] 志愿者招募 （费用流） [NOI2008] 志愿者招募 （费用流） 题目描述

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要 n n n 天才能完成，其中第 i i i 天至少需要 a i a_i ai​ 个人。布布通过了解得知，一共有 m m m 类志愿者可以招募。其中第 i i i 类可以从第 s i s_i si​ 天工作到第 t i t_i ti​ 天，招募费用是每人 c i c_i ci​ 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

输入输出格式 输入格式

第一行包含两个整数 n , m n,m n,m，表示完成项目的天数和可以招募的志愿者的种类。接下来的一行中包含 n n n 个非负整数，表示每天至少需要的志愿者人数。 接下来的 m m m 行中每行包含三个整数 s i , t i , c i s_i, t_i, c_i si​,ti​,ci​，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的

输出格式

仅包含一个整数，表示你所设计的最优方案的总费用。

输入输出样例 输入样例 #1

3 3
2 3 4
1 2 2
2 3 5
3 3 2

输出样例 #1

14

说明

1 ≤ n ≤ 1000 1leq nleq 1000 1≤n≤1000， 1 ≤ m ≤ 10000 1leq mleq 10000 1≤m≤10000，题目中其他所涉及的数据均不超过 2 31 − 1 2^{31}-1 231−1。

思路

对于本题我们可以进行如下假设：
第i天工作的志愿者人数为 P i P_i Pi​，第i种志愿者的人数为 X i X_i Xi​，第i天至少需要的志愿者人数为 a i a_i ai​
那么我们能不失一般性的列出类似以下方程组:
P 1 = X 1 + X 2 ≥ a 1 P 2 = X 1 + X 3 ≥ a 2 P 3 = X 3 ≥ a 3 begin{aligned} P_1 &= X_1 + X_2 &geq a_1\ P_2 &=X_1 + X_3& geq a_2\ P_3 &= X_3 &geq a_3 end{aligned} P1​P2​P3​​=X1​+X2​=X1​+X3​=X3​​≥a1​≥a2​≥a3​​
接下来设置一组非负整数 Y i Y_i Yi​，并加入两个特殊的等式
P 0 = 0 P 1 = X 1 + X 2 − Y 1 = a 1 P 2 = X 1 + X 3 − Y 2 = a 2 P 3 = X 3 − Y 3 = a 3 P 4 = 0 begin{aligned} P_0 &= 0\ P_1 &= X_1 + X_2 -Y_1 &= a_1\ P_2 &=X_1 + X_3 -Y_2 &= a_2\ P_3 &= X_3 - Y_3 &=a_3\ P_4 &= 0 end{aligned} P0​P1​P2​P3​P4​​=0=X1​+X2​−Y1​=X1​+X3​−Y2​=X3​−Y3​=0​=a1​=a2​=a3​​
我们对每一个等式与前一个等式做差
P 1 − P 0 = X 1 + X 2 − Y 1 = a 1 P 2 − P 1 = X 3 − X 2 + Y 1 − Y 2 = a 2 − a 1 P 3 − P 2 = − X 1 + Y 2 − Y 3 = a 3 − a 2 P 4 − P 3 = − X 3 + Y 3 = − a 3 begin{aligned} P_1- P0 &= X_1 + X_2 -Y_1 &= a_1\ P_2-P_1 &= X_3-X_2 +Y_1-Y_2 &= a_2 - a_1\ P_3 -P_2&= -X_1+Y_2 - Y_3 &= a_3-a_2\ P_4 -P_3&= -X_3 +Y_3 &=-a_3 end{aligned} P1​−P0P2​−P1​P3​−P2​P4​−P3​​=X1​+X2​−Y1​=X3​−X2​+Y1​−Y2​=−X1​+Y2​−Y3​=−X3​+Y3​​=a1​=a2​−a1​=a3​−a2​=−a3​​
我们将所有的变量和常数移到同一侧
− X 1 − X 2 + Y 1 + a 1 = 0 − X 3 + X 2 − Y 1 + Y 2 + a 2 − a 1 = 0 X 1 − Y 2 + Y 3 + a 3 − a 2 = 0 − X 3 + Y 3 − a 3 = 0 begin{aligned} -X_1 - X_2 +Y_1 + a_1 &= 0 \ -X_3+X_2 -Y_1+Y_2 +a_2 - a_1&=0 \ X_1-Y_2 + Y_3 +a_3-a_2 &= 0\ -X_3 +Y_3 -a_3 &= 0 end{aligned} −X1​−X2​+Y1​+a1​−X3​+X2​−Y1​+Y2​+a2​−a1​X1​−Y2​+Y3​+a3​−a2​−X3​+Y3​−a3​​=0=0=0=0​
如果我们把每个式子中的正负号与流入流出相类比，那么这显然就是一个网络流，那么按照网络流建图，变量流量为INF，常数则由源点流入或由汇点流出。由于我们还要求我们的费用最小，所以X变量具有价值。
至此，利用MCMF即可求得答案。

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e3+5 , M = 4e4+5 , INF = 0x3f3f3f3f;
int tot,head[N],nxt[M],to[M],w[M],c[M],dis[N],cur[N];
bool inq[N],vis[N];
int n,m,s,t,P[N];

void add_edge(int a,int b,int x,int y)
{
    nxt[++tot] = head[a] , head[a] = tot , to[tot] = b , w[tot] = x ,c[tot] = y;
    nxt[++tot] = head[b] , head[b] = tot , to[tot] = a , w[tot] = 0 ,c[tot] = -y;
}

bool spfa()
{
    memset(dis,0x3f,sizeof(dis));
    memcpy(cur,head,sizeof(head));
    memset(inq,0,sizeof(inq));
    memset(vis,0,sizeof(vis));
    queue q;
    dis[s] = 0;
    inq[s] = 1;
    q.push(s);
    while(q.size())
    {
        int x = q.front();
        q.pop();
        inq[x] = 0;
        for(int i = head[x] ; ~i ; i = nxt[i])
        {
            int y = to[i] , vol = w[i] , cost = c[i];
            if( vol > 0 && dis[y] > dis[x] + cost)
            {
                dis[y] = dis[x] + cost;
                if(!inq[y])
                {
                    q.push(y);
                    inq[y] = 1;
                }
            }
        }
    }
    return dis[t] != INF;
}

int dfs(int x = s ,int flow = INF )
{
    if(x == t)
        return flow;
    vis[x] = 1;
    int rest = flow;
    for(int & i = cur[x] ; ~i && rest ; i = nxt[i])
    {
        int y = to[i] , vol = w[i] , cost = c[i];
        if(vol > 0 && !vis[y] && dis[y] == dis[x] + cost)
        {
            int maxflow = dfs(y,min(rest,vol));
            rest -= maxflow;
            w[i] -= maxflow;
            w[i^1] += maxflow;
        }
    }
    return flow - rest;
}

int MCMF()
{
    int ans = 0;
    while(spfa())
    {
        ans += dfs() * dis[t];
    }
    
    return ans;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(head,-1,sizeof(head));
    tot = -1;
    s = 0 , t = n + 3;
    for(int i = 1 ; i <= n ; i ++)
    {
        scanf("%d", P+i);
    }
    for(int i = 1 ; i <= m ; i ++)
    {
        int l,r,C;
        scanf("%d%d%d",&l,&r,&C);
        add_edge(l,r+1,INF,C);
    }
    for(int i = 1 ; i <= n + 1; i ++)
    {
        if(P[i] - P[i-1] >= 0)
            add_edge(s,i,P[i]-P[i-1],0);
        else
            add_edge(i,t,P[i-1]-P[i],0);
        if(i > 1)
            add_edge(i,i-1,INF,0);
    }
    printf("%d",MCMF());
    return 0;
}