费用流求助(码风良好)
查看原帖
费用流求助(码风良好)
300166
Zikl楼主2023/3/25 21:44

40分,大样例WA了,没有输出。

大样例

应输出 83144953114,我没输出........

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
const int inf=1<<30;
using namespace std;
int n,ct,s=0,t=300005,p,m1,f,n1,ss,ans;
int head[500005],ver[500005],Next[500005],edg[500005],cost[500005],tot=1;
void add(int x,int y,int z,int c){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot,edg[tot]=z,cost[tot]=c;
	ver[++tot]=x,Next[tot]=head[y],head[y]=tot,edg[tot]=0,cost[tot]=-c;
}
int pre[500005],dis[500005],incf[500005],inq[500005];
int spfa(){
	for(int i=0;i<=500005;i++) dis[i]=inf,inq[i]=0;
	queue<int>q;
	q.push(s);
	inq[s]=1;
	dis[s]=0;
	incf[s]=inf;
	while(q.size()){
		int x=q.front();
		q.pop();
		inq[x]=0;
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i];
			if(!edg[i]) continue;
			if(dis[y]>dis[x]+cost[i]){
				dis[y]=dis[x]+cost[i];
				incf[y]=min(incf[x],edg[i]);
				pre[y]=i;
				if(!inq[y]){
					inq[y]=1;
					q.push(y);
				}
			}
		}
	}
	return dis[t]!=inf;
}
void Update(){
	int x=t;
	while(x!=s){
		int i=pre[x];
		edg[i]-=incf[t];
		edg[i^1]+=incf[i];
		x=ver[i^1];
	}
	ans+=dis[t]*incf[t]; 
}
signed main(){
	freopen("EK.in","r",stdin);
	freopen("EK.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ct;
		add(s,i,ct,0); add(i+n,t,ct,0);
	} 
	cin>>p>>m1>>f>>n1>>ss;
	for(int i=1;i<=n;i++){
		if(i+1<=n)
		add(i,i+1,inf,0);
		if(i+m1<=n)
		add(i,i+n+m1,inf,f);
		if(i<=n1)
		add(i,i+n+n1,inf,ss);
		add(s,i+n,inf,p);
	}
	while(spfa()){
		Update();
	}
	cout<<ans;
	return 0;
}

赏一关注,谢谢大佬! qwq

2023/3/25 21:44
加载中...