每日一题-P1251

网络流24题~

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf=1e9;
const ll lnf=1e18;
int N,p,m,f,n,s,r[2005],st,ed;
struct edge{
	int v,nx;ll w;int c;
}e[40005];
int cnt,hd[4105];
void add(int u,int v,ll w,int c){
	e[++cnt]=edge{v,hd[u],w,c};
	hd[u]=cnt;
}
void add_edge(int u,int v,ll w,int c){
	add(u,v,w,c);add(v,u,0,-c);
} 
ll flow[4105];
int dis[4105],pre[4105];
bool vis[4105];
bool spfa(){
	queue<int> q;q.push(st);
	memset(dis,0x3f,sizeof(dis));
	memset(flow,0,sizeof(flow));
	memset(vis,0,sizeof(vis));
	dis[st]=0;flow[st]=lnf;
	while(!q.empty()){
		int u=q.front();q.pop();
		vis[u]=0;
//		printf("%d\n",u);
		for(int i=hd[u];i;i=e[i].nx){
//			printf(" %d %lld %d\n",e[i].v,e[i].w,e[i].c);
			int v=e[i].v;if(e[i].w<=0 || dis[v]<=dis[u]+e[i].c)continue;
			dis[v]=dis[u]+e[i].c;flow[v]=min(flow[u],e[i].w);pre[v]=i;
			if(!vis[v])vis[v]=1,q.push(v);
		}
	}
//	for(int i=1;i<=ed;i++)printf("%d ",dis[i]);puts("");
	return dis[ed]!=0x3f3f3f3f;
}
inline int id(int i){
	if(i&1)return i+1;
	else return i-1;
}
void work(){
	ll res=0,sum=0;
	while(spfa()){
		res+=flow[ed];sum+=dis[ed]*flow[ed];
		int u=ed;
		while(u!=st){
			int i=pre[u];
			e[i].w-=flow[ed];e[id(i)].w+=flow[ed];
			u=e[id(i)].v;
		}
	}
	printf("%lld\n",sum);
}
int main(){
	scanf("%d",&N);
	for(int i=1;i<=N;i++)scanf("%d",&r[i]);
	scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
	st=N+N+1,ed=N+N+2;
	for(int i=1;i<=N;i++)add_edge(st,i+N,r[i],0),add_edge(i,ed,r[i],0);
	for(int i=1;i<=N;i++){
		if(i<N)add_edge(i+N,i+N+1,lnf,0);
		if(i<=N-m)add_edge(i+N,i+m,lnf,f);
		if(i<=N-n)add_edge(i+N,i+n,lnf,s);
		add_edge(st,i,lnf,p);
	}
	work();
	return 0;
}