MnZn求助费用流
查看原帖
MnZn求助费用流
285617
黑影洞人楼主2022/10/5 14:14
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define N 1919810
#define inf 0x3f3f3f3f
using namespace std;
int n,m1,m2,a[N],b[N],s,t;
int head[N],to[N],nxt[N],val[N],cst[N],tot=1;
int dis[N],ansc,ans1,ans2;
bool vis[N];
void add(int u,int v,int w,int c){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
	val[tot]=w;
	cst[tot]=c;
	to[++tot]=u;
	nxt[tot]=head[v];
	head[v]=tot;
	val[tot]=0;
	cst[tot]=-c;
}
bool spfa(){
	queue<int>q;
	q.push(s);
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=nxt[i]){
			if(!val[i])continue;
			int y=to[i],w=cst[i];
			if(dis[y]>dis[x]+w){
				dis[y]=dis[x]+w;
				if(!vis[y])vis[y]=1,q.push(y);
			}
		}
	}
	return dis[t]!=inf;
}
int dfs(int x,int a){
	if(x==t||!a)return a;
	int res=a;
	vis[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i],w=cst[i];
		if(val[i]&&!vis[y]&&dis[y]==dis[x]+w){
			int tmp=dfs(y,min(res,val[i]));
			res-=tmp;
			val[i]-=tmp;
			val[i^1]+=tmp;
			ansc+=tmp*w;
			if(res<=0){
				vis[x]=0;
				return a;
			}
		}
	}
	vis[x]=0;
	if(res==a)vis[x]=1;
	return a-res;
}
void dinic(){
	while(spfa()){
		memset(vis,0,sizeof(vis));
		while(dfs(s,n));
	}
}
signed main(){
	scanf("%d%d%d",&n,&m1,&m2);
	s=N-2,t=N-1;
	for(int i=1;i<=m1;i++)scanf("%d",&a[i]),add(s,i,1,a[i]);
	for(int i=1;i<=m1;i++)add(i,t,inf,0);
	dinic();
	ans1=ansc;
	ansc=0;
	memset(head,0,sizeof(head));
	tot=0;
	for(int i=1;i<=m1;i++)add(s,i,1,a[i]);
	for(int i=1;i<=m2;i++){
		scanf("%d",&b[i]);
		for(int j=1;j<=m1;j++)add(j,i+m1,1,b[i]);
		add(i+m1,t,inf,0);
	}
	dinic();
	printf("%d %d",ans1,ansc);
	return 0;
}



2022/10/5 14:14
加载中...