969. 志愿者招募

969. 志愿者招募

关键

费用怎么构造的不是很懂，但是是个无源汇上下界可行流，先记着，感觉很不错的题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e6+5,inf=1e9;
 
int h[N],ne[M],e[M],w[M],c[M],tot=1;
void add(int from,int to,int wi,int ci) {
    e[++tot]=to;  w[tot]=wi;  c[tot]=ci;  ne[tot]=h[from];  h[from]=tot;
    e[++tot]=from;w[tot]=0;   c[tot]=-ci; ne[tot]=h[to];    h[to]=tot;
}
 
int S=N-2,T=N-1;
bool st[N];
int dis[N],flow[N],pre[N];
bool spfa() {
    memset(dis,0x3f,sizeof(dis));
    memset(flow,0,sizeof(flow));
    queue<int>q;q.push(S);
    flow[S]=inf;dis[S]=0;st[S]=1;
    while(!q.empty()) {
        int now=q.front();
        q.pop();st[now]=0;
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            if(w[i]>0&&dis[to]>dis[now]+c[i]) {
                dis[to]=dis[now]+c[i];
                pre[to]=i;
                flow[to]=min(flow[now],w[i]);
                if(st[to]==0)st[to]=1,q.push(to);
            }
        }
    }
    return flow[T];
}
 
int EK() {
    int ans=0;
    while(spfa()) {
        int tmp=flow[T];
        ans+=tmp*dis[T];
        for(int i=T;i!=S;i=e[pre[i]^1]) {
            w[pre[i]]-=tmp;
            w[pre[i]^1]+=tmp;
        }
    }
    return ans;
}

int main() {
    int n,m;
    cin>>n>>m;
    int last=0;
    for(int i=1;i<=n;i++) {
        int x;cin>>x;
        if(last>x)add(S,i,last-x,0);
        else if(last<x)add(i,T,x-last,0);
        add(i,i+1,inf-x,0);
        last=x;
    }
    add(S,n+1,last,0);
    while(m--) {
        int a,b,c;
        cin>>a>>b>>c;
        add(b+1,a,inf,c);
    }
    cout<<EK();
    return 0;
}
//很迷的题目，但是感觉很好