C++(g++ 7.5.0) 解法, 执行用时: 79ms, 内存消耗: 684K, 提交时间: 2022-09-02 17:58:23

#include<bits/stdc++.h>
using namespace std ;
const int N = 5005, M = 100005, INF = 1<<30 ;
struct Edge
{
    int nxt,to,c,cost ;
}e[M] ;
int head[N],d[N],tot=1 ;
int S,T ;
queue<int>q ;
bool inq[N],vis[N] ;
void add(int from,int to,int c,int cost)
{
    e[++tot].to=to ; e[tot].c=c ; e[tot].cost=cost ; e[tot].nxt=head[from] ; head[from]=tot ;
    e[++tot].to=from ; e[tot].c=0 ; e[tot].cost=-cost ;  e[tot].nxt=head[to] ; head[to]=tot ;
}
bool spfa()
{
    while(!q.empty()) q.pop() ;
    for(int i=1;i<=T;++i) d[i]=INF,inq[i]=vis[i]=0 ;
    q.push(S) ; d[S]=0 ; inq[S]=1 ;
    while(!q.empty())
    {
        int x=q.front() ; q.pop() ; inq[x]=0 ;
        for(int i=head[x];i;i=e[i].nxt)
        {
            if(!e[i].c) continue ;
            int y=e[i].to ;
            if(d[y]>d[x]+e[i].cost)
            {
                d[y]=d[x]+e[i].cost ;
                if(!inq[y]) q.push(y),inq[y]=1 ;
            }
        }
    }
    return d[T]<INF ;
}
int maxflow=0,ans=0 ;
// maxflow -> 最大流
// ans -> 最小费用
int dinic(int x,int flow)
{
    if(x==T)
    {
        maxflow+=flow ;
        ans+=flow*d[T] ;
        return flow ;
    }
    vis[x]=1 ;
    int rest=flow,k ;
    for(int i=head[x];i;i=e[i].nxt)
    {
        if(!e[i].c||vis[e[i].to]) continue ;
        int y=e[i].to ;
        if(d[y]==d[x]+e[i].cost)
        {
            k=dinic(y,min(e[i].c,rest)) ;
            e[i].c-=k ; e[i^1].c+=k ; rest-=k ;
            if(!rest) break ;
        }
    }
    return flow-rest ;
}
//main
int sum,n,m,s,f,p ;
int r[N] ;

int main()
{
    cin>>sum>>p>>m>>f>>n>>s ;
    for(int i=1;i<=sum;++i) cin>>r[i] ;
    S=sum*2+1 ; T=S+1 ; 
    for(int i=1;i<=sum;++i)
    {
        add(S,i,INF,p),add(i,T,r[i],0) ;
        if(i>1) add(S,i+sum,r[i-1],0) ;
        if(i<sum) add(i,i+1,INF,0),add(i+sum,i+sum+1,INF,0) ;
        if(i>=n) add(i-n+sum+1,i,INF,s) ;
        if(i>=m) add(i-m+sum+1,i,INF,f) ;
    }
    while(spfa()) dinic(S,INF) ;
    cout<<ans<<'\n' ;
    return 0 ;
}

C++(clang++ 11.0.1) 解法, 执行用时: 121ms, 内存消耗: 1000K, 提交时间: 2023-01-02 14:15:03

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int M = 5e5 + 10, INF = 1e8;
int h[10010], e[M], ne[M], f[M], w[M], idx, d[10010], incf[10010], n, m, S, T, pre[10010], N, p, F, s;
bool st[10010];
void add(int a, int b, int c, int d)
{
	e[idx] = b, ne[idx] = h[a], f[idx] = c, w[idx] = d, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = 0, w[idx] = -d, h[b] = idx ++;
}

bool spfa()
{
	queue<int>q;
	memset(d, 0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	d[S] = 0;
	incf[S] = INF;
	q.push(S);

	while(!q.empty())
	{
		auto t = q.front();
		q.pop();
		st[t] = false;
		for(int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if(d[j] > d[t] + w[i] && f[i])
			{
				d[j] = d[t] + w[i];
				pre[j] = i;
				incf[j] = min(incf[t], f[i]);
				if(!st[j])
				{
					st[j] = 1;
					q.push(j);
				}
			}
		}
	}
	return incf[T] > 0;
}	

int EK()
{
	int flow = 0, cost = 0;
	while(spfa())
	{
		flow += incf[T];
		cost += incf[T] * d[T];
		for(int i = T; i != S; i = e[pre[i] ^ 1])
		{
			f[pre[i]] -= incf[T];
			f[pre[i] ^ 1] += incf[T];
		}
	}
	return cost;
}
typedef pair<int, int>PII;
int a[2010];


signed main()
{
	cin >> N >> p >> m >> F >> n >> s;
	memset(h, -1, sizeof h);
	for(int i = 1; i <= N; i ++ ) cin >> a[i];

	S = 0, T = N * 2 + 1;

	for(int i = 1; i <= N; i ++ )
	{
		add(S, i, a[i], 0);
		add(i + N, T, a[i], 0);
		add(S, i + N, INF, p);
		if(i - m >= 1) add(i - m, i + N, INF, F);
		if(i - n >= 1) add(i - n, i + N, INF, s);
		if(i - 1 >= 1) add(i - 1, i, INF, 0);
	}

	cout << EK() << '\n';
}