题解：P2223 [HNOI2001] 软件开发

海洋守卫者 · 2025-05-07 16:51:25 · 题解

P2223 [HNOI2001] 软件开发

双倍经验

解题思路

由于消毒毛巾在天数之间是流动的，因此可以想到最小费用最大流。考虑建图，将新的毛巾与旧毛巾分开来算，即将白天与晚上分开。

一、处理新的消毒毛巾和旧的消毒毛巾

• 购买新消毒毛巾：从超级源点 S 直接向每天白天连边，流量为 +\infty，费用为 f。
• A 种消毒方式：从第 i 天向第 i+a+1 天连边，流量为 +\infty，费用为 f_A。
• B 种消毒方式：同理，从第 i 天向第 i+b+1 天连边，流量为 +\infty，费用为 f_B。
• 每天产生的旧消毒毛巾：因为每天使用的消毒毛巾数量是固定的，所以每天产生的旧消毒毛巾数量也是固定的，我们可以从超级源点 S 直接向每天晚上连边，流量为 n_i，费用为 0。

二、处理每天使用新消毒毛巾的数量

要使每天使用的消毒毛巾的数量固定，可以将每天白天使用的新消毒毛巾流向超级汇点 T，最终的最大流量就为所有天中使用的消毒毛巾个数之和，保证了数量的稳定。

完整代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN=5e4+5,oo=0x3f3f3f3f;
int n,a,b,p,f,s,k,S,T,h[MAXN],ec=1;
long long ans,sum;
struct Edge{
    int u,v,w,c,nxt;
}e[MAXN<<2];
inline void AddEdge(int u,int v,int w,int c)
{
    e[++ec]={u,v,w,c,h[u]};
    h[u]=ec;
}
inline void Add(int u,int v,int w,int c)
{
    AddEdge(u,v,w,c);
    AddEdge(v,u,0,-c);
}
int vis[MAXN],dis[MAXN];
queue<int>que;
bool SPFA(int s,int t){
    while(!que.empty())que.pop();
    memset(vis,0,sizeof vis);
    memset(dis,0x3f,sizeof dis);
    vis[t]=1,que.push(t),dis[t]=0;
    while(!que.empty()){
        int u=que.front();que.pop();
        vis[u]=0;
        for(int i=h[u];i;i=e[i].nxt){
            if(e[i^1].w&&dis[u]+e[i^1].c<dis[e[i].v]){
                dis[e[i].v]=dis[u]+e[i^1].c;
                if(vis[e[i].v])continue;
                que.push(e[i].v);
                vis[e[i].v]=1;
            }
        }
    }
    return dis[s]!=oo;
} 
int DFS(int u, int t, int f){ 
    if(u==t||!f)return f;
    vis[u]=1;
    int rest=f;
    for(int i=h[u];i;i=e[i].nxt){
        if(dis[e[i].v]!=dis[u]-e[i].c||!e[i].w||vis[e[i].v])continue;
        int tmp=DFS(e[i].v,t,min(e[i].w,rest));
        if(!tmp){
            dis[e[i].v]=oo;
            continue;
        }
        e[i].w-=tmp;
        e[i^1].w+=tmp;
        rest-=tmp;
        if(!rest)return f;
    }
    vis[u]=0;
    return f-rest;
}
void ZKW(int s,int t){ 
    ans=sum=0;
    while(SPFA(s,t)){
        memset(vis,0,sizeof vis);
        int tmp=DFS(s,t,oo);
        ans+=tmp;sum+=1ll*tmp*dis[s];
    }
}

main()
{
    scanf("%d %d %d %d %d %d",&n,&a,&b,&p,&f,&s);
    S=1,T=2*n+2;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%lld",&x);
        Add(S,i<<1|1,x,0);
        Add(i<<1,T,x,0);
    }
    for(int i=1;i<=n;i++)
    {
        if(i+1<=n)Add(i<<1|1,i+1<<1|1,oo,0);
        if(i+a+1<=n)Add(i<<1|1,i+a+1<<1,oo,f);
        if(i+b+1<=n)Add(i<<1|1,i+b+1<<1,oo,s);
        Add(S,i<<1,oo,p);
    }
    ZKW(S,T);
    printf("%lld",sum);
    return 0;
}