P3980 [NOI2008] 志愿者招募

题意

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

题解

这道题的建图好妙啊，以前没有见过，想多做几道类似的题，目前还不会上下界网络流，之后再补。
首先看完题目我们可以想到一个比较经典的想法，源点向人连边，人向天连边，天向汇点连边。
但这样有些问题，我们不是很好的处理流量与费用之间的关系。
这里有一个比较新奇的建边方式，可以规避一些问题。
1.源点向第 \(1\) 天连一条，流 \(0\)，费 \(0\) 的边。
2.第 \(i\) 天向 \(i+1\) 天连接一条流 \(i+1\)天连一条流 \(-a_i\),费 \(0\) 的边。
3.对于每个人的 \(s_i\) 天向 \(t_i\) 连一条流 \(0\) ,费 \(c_i\) 的边。
4.第 \(n+1\) 条边连向汇点一条流 \(0\)，费 \(0\) 的边。

这为什么是对的呢，我们来仔细分析一下。
首先我们知道费用流会优先走费用小的边，这道题的连边方式会让所有负边都流空，所以我们假设走完所有天之间的边之后的总流为 \(\sum -a_i\)。
但是显然我们这张图的最大流为 \(0\) ，所以我们接下来我们会通过走第 \(3\) 类边将总流重新填回 \(0\)。
而我们实际上是在天的边和人的边做选择，这也是 \(s_i\) 向 \(t_i+1\) 连的这条边和之间的边作选择，同时也保证了一个人直接做了一个区间。
最后由于最大流不能是负数，所以我们给所有的边的流量加上 \(INF\) ，由于我们是对差跑网络流，所以是不影响的。

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
const int N = 1e6+5 ;
const int INF = 1e9+7 ;
int n,m,s,t,ans1,ans2,clow,cnt = 1 ;
int dis[N],vis[N],a[N] ;
struct Edge{int v,c,w ;}E[N] ;
vector<int>e[N] ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
    x = 0 ;rg int f(0) ; rg char c(gc()) ;
    while(!isdigit(c)) f |= (c=='-'),c = gc() ;
    while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
    x = (f?-x:x) ;
    read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
    if(x < 0) pc('-'),x = -x ;
    do stk[++tp] = x%10,x /= 10 ; while(x) ;
    while(tp) pc(stk[tp--]^48) ; space ;
    print(p...) ;
}
inline void Add(int u,int v,int c,int w)
{
    E[++cnt] = {v,c,w},e[u].pb(cnt) ;
    E[++cnt] = {u,-c,0},e[v].pb(cnt) ;
}
inline int Bfs()
{
    queue<int>q ; q.push(s),me(dis,0x3f),dis[s] = 0 ;
    while(!q.empty())
    {
        int x = q.front() ; q.pop() ;
        for(auto id:e[x])
        {
            auto [v,c,w] = E[id] ;
            if(dis[v] <= dis[x]+c || !w) continue ;
            dis[v] = dis[x]+c,q.push(v) ;
        }
    }
    return dis[t]!=dis[0] ;
}
int Dfs(int x,int flow)
{
    if(x == t) return flow ;
    int us = 0 ; vis[x] = 1 ;
    for(auto id:e[x]) 
    {
        auto &[v,c,w] = E[id] ;
        if(dis[x]+c != dis[v] || !w || vis[v]) continue ;
        int low = Dfs(v,min(flow-us,w)) ;
        if(low) w -= low,E[id^1].w += low,us += low ; 
        if(us == flow) break ;
    }
    if(!us) dis[x] = dis[0] ;
    return us ;
}
signed main()
{
//	freopen(".in","r",stdin) ;
//	freopen(".out","w",stdout) ;
    read(n,m) ;
    s = n+2,t = s+1 ; //print(n,m),enter ;
    FOR(i,1,n,1) read(a[i]),Add(i,i+1,0,INF-a[i]) ;
    FOR(i,1,m,1)
    {

        int si,ti ; read(si,ti,a[i]) ;
        Add(si,ti+1,a[i],INF) ;
    }
    Add(s,1,0,INF),Add(n+1,t,0,INF) ;
    while(Bfs())
    {
        me(vis,0) ;
        clow = Dfs(s,INF*2),ans1 += clow,ans2 += clow*dis[t] ;
    } 
    print(ans2) ;
    return 0 ;
}