萌新求助,30pts,wa
查看原帖
萌新求助,30pts,wa
122794
tuya_楼主2021/1/9 23:37
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=100010;
const int maxm=300100;
#define inf 2147483647
#define ll long long
int n,m,f,s,p,N;
ll r[maxn];
long long flow[maxm],size[maxm],pay[maxm];
int u[maxm],v[maxm],fir[maxm],nex[maxm];
int day[maxn],nig[maxn];
//每天白天的节点,晚上的节点;
int end,top=-1;
//节点总数,边总数
//起点,终点,总流量,费用 
void add(int a,int b,ll c,int d){
	top++;
	u[top]=a;v[top]=b;size[top]=c;flow[top]=0;
	pay[top]=d;nex[top]=fir[a];fir[a]=top;
	
	top++;
	u[top]=b;v[top]=a;size[top]=0;flow[top]=0;
	pay[top]=-d;nex[top]=fir[b];fir[b]=top;
} 
queue<int>q;
bool vis[maxn];
int pre[maxn],pos[maxn];
long long dis[maxn];
bool spfa(){
	q.push(0);
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=end;i++) dis[i]=(ll)inf;
	vis[0]=1;
	dis[0]=0;
	while(q.size()){
		int now=q.front();
		q.pop();
		vis[now]=0;
		for(int j=fir[now];j!=-1;j=nex[j]){
			int to=v[j];
			//cout<<now<<" "<<to<<" "<<size[j]<<" "<<flow[j]<<endl;
			if(dis[to]>dis[now]+pay[j] && size[j]>flow[j]){
				dis[to]=dis[now]+pay[j];
				pre[to]=now;
				pos[to]=j;
				if(!vis[to]) {
					q.push(to);
					vis[to]=true;
				}
			}
		}
	}
	if(dis[end]!=(ll)inf) return true; 
	return false;
}

long long ans=0;
void work(){
	while(spfa()){
		//cout<<"ww"<<endl;
		ll mi=inf;
		for(int i=end;i!=0;i=pre[i]){
			mi=min((ll)mi,size[pos[i]]-flow[pos[i]]);
		}
		ans+=mi*dis[end];
		for(int i=end;i!=0;i=pre[i]){
			flow[pos[i]]+=mi;
			flow[pos[i^1]]-=mi;
		}
	}
}
int main(){
	//freopen("1.txt","r",stdin);
	memset(fir,-1,sizeof fir);
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%lld",&r[i]);
	scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
	for(int i=1;i<=N;i++){
		day[i]=++end;
		nig[i]=++end;
	}
	end++;
	for(int i=1;i<=N;i++){
		add(0,day[i],inf,p);		
		add(day[i],end,r[i],0);
		
		add(0,nig[i],r[i],0);
		if(i+1<=N) add(nig[i],nig[i+1],inf,0);
		if(i+m<=N)add(nig[i],day[i+m],inf,f);
		if(i+n<=N)add(nig[i],day[i+n],inf,s);
	}
	work();
	printf("%lld",ans);
	return 0;
}

求助大佬,过了1,6,7个点

2021/1/9 23:37
加载中...