洛谷(餐巾计划问题)

链接：https://www.luogu.org/problemnew/show/P1251
思路：费用流题目，建图还是关键，首先很显然想到了拆点，因为有用掉和送出去两个状态，所以把每天拆为两个点，一个表示使用量，一个表示送出去的量，分别放在二分图的x和y上，建立源点汇点，对于每个点i，从源点到x上的i建立一条容量c[i]，费用为0的边，表示当天使用c[i]个餐巾;从y轴上的i到汇点建立一条容量为c[i]，费用为p的边，用来限制最大流。然后对于每个x上的点，向x+1建立一条容量为INF，费用为0的边，向y+m上建立一条容量为INF，费用为f的边，向y+n上建立一条容量为INF，费用为s的边，最后跑一遍费用流即可。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5050;
const int INF = 1e9;

int t;
int c[2010];
int p,m,f,n,s;

struct edge{
    int from,to,cap,flow,cost;
};

struct MCMF{
    int n,m,s,t;
    vector<edge> edges;
    vector<int> G[maxn];
    int d[maxn];
    int inq[maxn];
    int p[maxn];
    int a[maxn];

    void init(int n){
        this->n = n;
        for(int i=0;i<=n;i++)G[i].clear();
        edges.clear();
    }

    void addedge(int from,int to,int cap,int cost){
        edges.push_back(edge{from,to,cap,0,cost});
        edges.push_back(edge{to,from,0,0,-cost});
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool spfa(int s,int t,int &flow,long long &cost){
        for(int i=0;i<=n;i++)d[i] = INF;
        memset(inq,0,sizeof(inq));
        d[s] = 0;
        inq[s] = 1;
        p[s] = 0;
        a[s] = INF;
        queue<int> q;
        q.push(s);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for(int i=0;i<G[u].size();i++){
                edge &e = edges[G[u][i]];
                if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u],e.cap-e.flow);
                    if(!inq[e.to]){
                        q.push(e.to);
                        inq[e.to] =  1;
                    }
                }
            }
        }
            if(d[t]==INF)return false;
            flow+=a[t];
            cost+=1LL*d[t]*a[t];
            int u  = t;
            while(u!=s){
                edges[p[u]].flow+=a[t];
                edges[p[u]^1].flow-=a[t];
                u = edges[p[u]].from;
            }
            return true;
        }

        long long mincost(int s,int t){
            int flow = 0;
            long long cost = 0;
            while(spfa(s,t,flow,cost));
            return cost;
        }
}solver;

int main(){
    scanf("%d",&t);
    for(int i=1;i<=t;i++)scanf("%d",&c[i]);
    scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
    solver.init(2*t+1);
    for(int i=1;i<=t;i++){
        solver.addedge(0,i,c[i],0);
        solver.addedge(i+t,2*t+1,c[i],0);
        solver.addedge(0,i+t,INF,p);
        if(i!=t)solver.addedge(i,i+1,INF,0);
        if(i+m<=t)solver.addedge(i,i+t+m,INF,f);
        if(i+n<=t)solver.addedge(i,i+t+n,INF,s);
    }
    long long res = solver.mincost(0,2*t+1);
    printf("%lld\n",res);
    return 0;   
}