最大流与Dijkstra做费用流

#define out(i,a,now) for(int i=a.be[now],to=a.v[i];i;i=a.ne[i],to=a.v[i])
#define fo(i,a,b) for(i=a;i<=b;i++)
struct adj_list
{
	LL be[maxn],ne[maxm<<2],v[maxm<<2],w[maxm<<2],cnt;
	void init()
	{
		qk(be); cnt=1;
	}
	void add(LL x,LL y,LL z)
	{
		v[++cnt]=y;
		ne[cnt]=be[x];
		w[cnt]=z;
		be[x]=cnt;
	}
}v;
LL bfs()//标号
{
	queue<LL> q;
	q.push(t);
	qk(id);
	id[t]=1;
	while (!q.empty())
	{
		LL now=q.front();
		q.pop();
		if (now==s) break;
		out(i,v,now)
		if (v.w[i^1] && !id[to])
		{
			id[to]=id[now]+1;
			q.push(to);
		}
	}
	return id[s];//判断是否有可行流
}
LL dfs(LL now,LL flow)//寻找可行流
{
	if (now==t) return flow;
	LL miflow;
	out(i,v,now)
	{
		LL wei=v.w[i];
		if (wei && id[to]==id[now]-1)
		{
			miflow=dfs(to,min(flow,wei));
			if (miflow)
			{
				v.w[i]-=miflow;
				v.w[i^1]+=miflow;//增加反向边流量
				return miflow;
			}
		}
	}
	return 0;
}
LL dinic()
{
	LL res=0;
	while (bfs())
	{
		LL temp;
		while (temp=dfs(s,LLONG_MAX>>1))
			res+=temp;
	}
	return res;
}
int main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	LL i;
	LL x,y,z;
	v.init();
	fo(i,1,m)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		v.add(x,y,z);
		v.add(y,x,0);
	}
	LL ans=dinic();
	printf("%lld",ans);
}

#define out(i,a,now) for(int i=a.be[now],to=a.v[i];~i;i=a.ne[i],to=a.v[i])
#define fo(i,a,b) for(i=a;i<=b;i++)
struct adj_list
{
	LL be[maxn],ne[maxm<<4],v[maxm<<4],w[maxm<<4],c[maxm<<4],cnt;
	void init()
	{
		memset(be,-1,sizeof(be));
		cnt=0;
	}
	void add(LL pre,LL nxt,LL wei,LL cost)
	{
		v[cnt]=nxt;
		ne[cnt]=be[pre];
		be[pre]=cnt;
		w[cnt]=wei;
		c[cnt]=cost;
		++cnt;
	}
};
struct NetWork
{
	adj_list v;
	LL dis[maxn],h[maxn],pre_node[maxn],pre_edge[maxn],inque[maxn];
	void SPFA(LL be,LL en)
	{
		queue<LL> q;
		qk(inque);
		LL i;
		fo(i,1,n) h[i]=LLONG_MAX>>1;
		h[be]=0; inque[be]=1;
		q.push(be);
		while (!q.empty())
		{
			LL now=q.front();
			q.pop();
			out(i,v,now)
			if (h[now]+v.c[i]<h[to] && v.w[i])
			{
				h[to]=h[now]+v.c[i];
				if (!inque[to])
				{
					q.push(to);
					inque[to]=1;
				}
			}
			inque[now]=0;
		}
	}
	void MCMF(LL s,LL t,LL &flow,LL &cost)
	{
		flow=cost=0;
		SPFA(s,t);//用一次SPFA更新h数组
		while (1)
		{
			pre_node[s]=pre_edge[s]=-1;//开始堆优化dijkstra算法
			LL i;
			fo(i,1,n) dis[i]=LLONG_MAX>>1;
			dis[s]=0;
			priority_queue<Pair,vector<Pair>,greater<Pair> > pq;
			pq.push(mp(0,s));
			while(!pq.empty())
			{
				Pair now=pq.top();
				pq.pop();
				if (now.first!=dis[now.second]) continue;
				if (now.second==t) break;
				out(i,v,now.second)
				{
					LL len=v.c[i]+h[now.second]-h[to];
					if (v.w[i] && dis[now.second]+len<dis[to])
					{
						dis[to]=dis[now.second]+len;
						pq.push(mp(dis[to],to));
						pre_node[to]=now.second;//记录从哪个点来
						pre_edge[to]=i;//记录从哪条边来
					}
				}
			}
			if (dis[t]>=(LLONG_MAX>>1)) break;
			LL miflow=LLONG_MAX>>1;
			for(i=t;i!=s;i=pre_node[i])
				cmin(miflow,v.w[pre_edge[i]]);//找到路径上流量最小值
			for(i=t;~i;i=pre_node[i])
			{
				v.w[pre_edge[i]]-=miflow;
				v.w[pre_edge[i]^1]+=miflow;//更新反向边
			}
			flow+=miflow;
			cost+=miflow*(h[t]+dis[t]);
			fo(i,1,n) h[i]=min(h[i]+dis[i],LLONG_MAX>>1);//更新h数组
		}
	}
	void sol()
	{
		v.init();
		LL i,x,y,z,w;
		scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
		fo(i,1,m)
		{
			scanf("%lld%lld%lld%lld",&x,&y,&z,&w);
			v.add(x,y,z,w);
			v.add(y,x,0,-w);
		}
		LL flow,cost;
		MCMF(s,t,flow,cost);
		printf("%lld %lld",flow,cost);
	}
}solver;
int main()
{
	solver.sol();
	return 0;
}