BZOJ 1221 HNOI 2001 軟件開發/網絡流24題 餐巾計劃問題 最小費用最大流

BZOJ 1221 HNOI 2001 軟件開發/網絡流24題 餐巾計劃問題 最小費用最大流

題目大意：有一個軟件公司，每天需要給一些員工准備消毒毛巾，這些毛巾可以循環利用，但是需要消毒。可以將毛巾送去消毒，有兩種方式，A天fA花費，B天fB花費。或者還可以直接買新毛巾，問為了滿足員工的需求，至少需要花多少錢。

思路：經典的費用流問題。將每一天拆點，S向每一天<<1連邊，約束每一天需要多少毛巾；每一天<<1|1向T連邊，約束每一天需要的毛巾。每一天<<1向這一天清洗的毛巾能夠使用的那一天<<1|1，注意A和B。毛巾可以延後使用，那麼每一天<<1|1向(每一天+1)<<1|1連邊，表示延後使用。然後跑EK。

CODE：
 

#include 
#include 
#include 
#include 
#include 
#define MAX 2010
#define MAXE 100000
#define INF 0x3f3f3f3f
#define S 0
#define T (MAX - 1)
using namespace std;
#define max(a,b) ((a) > (b) ? (a):(b))
 
struct MinCostMaxFlow{
    int head[MAX],total;
    int next[MAXE],aim[MAXE],flow[MAXE],cost[MAXE];
     
    int from[MAX],p[MAX],f[MAX];
    bool v[MAX];
     
    MinCostMaxFlow():total(1) {}
     
    void Add(int x,int y,int f,int c) {
        next[++total] = head[x];
        aim[total] = y;
        flow[total] = f;
        cost[total] = c;
        head[x] = total;
    }
    void Insert(int x,int y,int f,int c) {
        Add(x,y,f,c);
        Add(y,x,0,-c);
    }
    bool SPFA() {
        static queue q;
        memset(f,0x3f,sizeof(f));
        memset(v,false,sizeof(v));
        while(!q.empty())   q.pop();
        q.push(S);
        f[S] = 0;
        while(!q.empty()) {
            int x = q.front(); q.pop();
            v[x] = false;
            for(int i = head[x]; i; i = next[i])
                if(flow[i] && f[aim[i]] > f[x] + cost[i]) {
                    f[aim[i]] = f[x] + cost[i];
                    if(!v[aim[i]]) {
                        v[aim[i]] = true;
                        q.push(aim[i]);
                    }
                    from[aim[i]] = x;
                    p[aim[i]] = i;
                }
        }
        return f[T] != INF;
    }
    int EdmondsKarp() {
        int re = 0;
        while(SPFA()) {
            int max_flow = INF;
            for(int i = T; i != S; i = from[i])
                max_flow = min(max_flow,flow[p[i]]);
            for(int i = T; i != S; i = from[i]) {
                flow[p[i]] -= max_flow;
                flow[p[i]^1] += max_flow;
            }
            re += f[T] * max_flow;
        }
        return re;
    }
}Solver;
 
int days,buy_cost,slow,slow_cost,fast,fast_cost;
 
int main()
{
    cin >> days >> slow >> fast >> buy_cost >> slow_cost >> fast_cost;
    ++slow,++fast;
    for(int x,i = 1; i <= days; ++i) {
        scanf("%d",&x);
        Solver.Insert(S,i << 1,x,0);
        Solver.Insert(i << 1|1,T,x,0);
        Solver.Insert(S,i << 1|1,INF,buy_cost);
    }
    for(int i = 1; i <= days; ++i) {
        if(i + slow <= days) Solver.Insert(i << 1,(i + slow) << 1|1,INF,slow_cost);
        if(i + fast <= days) Solver.Insert(i << 1,(i + fast) << 1|1,INF,fast_cost);
    }
    for(int i = 1; i < days; ++i)
        Solver.Insert(i << 1|1,(i + 1) << 1|1,INF,0);
    cout << Solver.EdmondsKarp() << endl;
    return 0;
}