P1251 餐巾计划问题

P1251 餐巾计划问题

关键

感觉是一个很好的题目，但是理解的还不是很深刻，很像一种减法
1.毛巾不会多买，因为是直接连向了y点，所以数量是保证的
2.把直接买的和向下传递进行分开，从而形成了一种减法，但是两者又互不干扰，也就是数量上是一定满足条件的

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+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];
}
 
ll EK() {
    ll ans=0;
    while(spfa()) {
        ll tmp=flow[T];
        ans+=1ll*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 a,b1,b2,c1,c2;
int d[M];
//很神奇的一个题目

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>d[i];
    cin>>a>>b1>>b2>>c1>>c2;
    for(int i=1;i<=n;i++) {
        add(S,i<<1|1,inf,a);
        add(S,i<<1,d[i],0);
        add(i<<1|1,T,d[i],0);
        if(i+1<=n)add(i<<1,(i+1)<<1,inf,0);     //留到下一天在洗
        if(i+b1<=n)add(i<<1,(i+b1)<<1|1,inf,b2);//在这里可以洗多少
        if(i+c1<=n)add(i<<1,(i+c1)<<1|1,inf,c2);
    }
    //如果他被洗掉了，那就直接送走了
    cout<<EK()<<endl;
    return 0;
}