打dinic的费用流蜜汁63,蒟蒻求助
查看原帖
打dinic的费用流蜜汁63,蒟蒻求助
327567
zhy_learn楼主2022/3/13 15:47
#include<bits/stdc++.h>
#define Fu(i,a,b) for(register int i=(a);i<=(b);i++)
#define Fd(i,a,b) for(register int i=(a);i>=(b);i--)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int n,m,s,t,fi[50005],cur[50005],mf,mc,cnt=1;
struct edge{
	int ne,to,f,w;
}e[1000005];
void add(int u,int v,int w,int f){
	e[++cnt].to=v,e[cnt].ne=fi[u],e[cnt].w=w,e[cnt].f=f,fi[u]=cnt;
	e[++cnt].to=u,e[cnt].ne=fi[v],e[cnt].w=0,e[cnt].f=-f,fi[v]=cnt;
}
int q[1000005],bj[50005],dis[50005],flow[50005],p[50005],l,r;
bool SPFA(){
	l=0,r=1;
	memset(bj,0,sizeof(bj));
	memset(dis,127/3,sizeof(dis));
	Fu(i,0,n) cur[i]=fi[i];
	flow[s]=0x7fffffff,q[1]=s,bj[s]=1,dis[s]=0;
	while(l<r){
		int u=q[++l];
		bj[u]=0;
		for(int i=fi[u];i;i=e[i].ne){
			int v=e[i].to;
			if(e[i].w&&dis[u]+e[i].f<dis[v]){
				dis[v]=dis[u]+e[i].f;
				if(!bj[v]) q[++r]=v,bj[v]=1;
			}
		}
	}
	return dis[t]!=dis[0];
}
int dfs(int u,int in){
	if(u==t||in==0) return in;
	int out=0;
	for(int &i=cur[u];i;i=e[i].ne){
		int v=e[i].to;
		if(e[i].w&&dis[v]==dis[u]+e[i].f){
			int o=dfs(v,min(in,e[i].w));
			e[i].w-=o;
			e[i^1].w+=o;
			in-=o,out+=o;
			mc+=o*e[i].f;
			if(in==0) break;
		}
	}
	if(out==0) dis[u]=-1;
	return out;
}
void MCMF(){
	int flow;
	while(SPFA())
		while((flow=dfs(s,0x7fffffff)))
			mf+=flow;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	Fu(i,1,m){
		int u,v,w,f;
		scanf("%d%d%d%d",&u,&v,&w,&f);
		add(u,v,w,f);
	} 
	MCMF();
	printf("%d %d",mf,mc);
	return 0;
}
2022/3/13 15:47
加载中...