蒟蒻在线求助网络流
查看原帖
蒟蒻在线求助网络流
293810
serene_analysis楼主2020/5/10 11:23

只有40,哪位大佬能帮忙看看? (注:除了建图应该都没问题,各位重点关注建图即可)

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define int long long
//#undef int

using std::queue;

int n;
int m,t1,m1,t2,m2;
//int s,t;
int st,en;
int x,y,z,w;

int h[50005],to[50005],next[50005],f[50005],c[50005];
int cnt=1;
void add(int x,int y,int z,int cost){
	to[++cnt]=y;
	next[cnt]=h[x];
	f[cnt]=z;
	c[cnt]=cost;
	h[x]=cnt;
}
void ad(int x,int y,int z,int cost){
	add(x,y,z,cost);
	add(y,x,-z,0);
}

int dis[50005],flow[50005],pre[50005],last[50005];
bool vis[50005];
bool spfa(){
	memset(dis,0x7f*1000,sizeof dis);
	memset(flow,0x7f*1000,sizeof flow);
	memset(vis,false,sizeof vis);
	queue<int>q;
	q.push(st);
	dis[st]=0;
	vis[st]=true;
	pre[en]=-1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=false;
		for(int i=h[x];i;i=next[i]){
			int v=to[i];
			if(f[i]>0&&dis[v]>dis[x]+c[i]){
				dis[v]=dis[x]+c[i];
				pre[v]=x;
				last[v]=i;
				flow[v]=std::min(flow[x],f[i]);
				if(!vis[v]){
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
	return ~pre[en];
}

int fl,co;
void mcmf(){
	while(spfa()){
		int u=en;
		fl+=flow[en];
		co+=flow[en]*dis[en];
		while(u!=st){
			f[last[u]]-=flow[en];
			f[last[u]^1]+=flow[en];
			u=pre[u];
		}
	}
}

signed main(){
//	freopen("st.txt","r",stdin);
	scanf("%lld",&n);
	st=0;
	en=2*n+1;
	for(int i=1;i<=n;i++){
		scanf("%lld",&x);
		ad(st,i,x,0);
		ad(i+n,en,x,0);
	}
	scanf("%lld%lld%lld%lld%lld",&m,&t1,&m1,&t2,&m2);
	for(int i=1;i<=n;i++){
		if(i+1<=n)ad(i,i+1,0x7f*1000,0);
		if(i+t1<=n)ad(i,i+n+t1,0x7f*1000,m1);
		if(i+t2<=n)ad(i,i+n+t2,0x7f*1000,m2);
		ad(st,i+n,0x7f*1000,m);
	}
	mcmf();
	printf("%lld",co);
	return 0;
}
2020/5/10 11:23
加载中...