最小费用最大流dij板子

本文主要是介绍最小费用最大流dij板子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

不说了，宏定义害死人

#include<bits/stdc++.h>
#define Pair pair<long long, long long>
#define fi first
#define se second
/*宏定义害死人*/
//#define AddEdge(x,y,f,z) add_edge(x,y,f,z);add_edge(y,x,0,-z);
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
// char buf[1<<20],*p1=buf,*p2=buf;
using namespace std;
const int NN=5010;
long long INF=1000000000000000000ll;
const int MM=50010;
inline int read()
{char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int N,M,S,T;//点数边数源点汇点
struct node
{int u,v;long long f,w;
}edge[MM];
int num=0;
vector<int>con[NN];
inline void add_edge(int x,int y,long long f,long long z)
{edge[num].u=x;edge[num].v=y;edge[num].f=f;edge[num].w=z;con[x].push_back(num);num++;
}
inline void AddEdge(int x,int y,long long f,long long z) {add_edge(x,y,f,z);add_edge(y,x,0,-z);}
long long h[NN],dis[NN];
int PrePoint[NN],PreEdge[NN];
Pair Dij()
{long long ansflow=0,anscost=0;for(int i=1;i<=N;i++)h[i]=0;//势能数组while(1){priority_queue<Pair>q;for(int i=1;i<=N;i++)dis[i]=INF;dis[S]=0;q.push(make_pair(0,S));while(q.size()!=0){Pair p=q.top();q.pop();if(-p.fi!=dis[p.se]) continue;if(p.se==T) break;int up=con[p.se].size();for(int ii=0;ii<up;ii++){int i=con[p.se][ii];long long nowcost=edge[i].w+h[p.se]-h[edge[i].v];if(edge[i].f>0&&dis[edge[i].v]>dis[p.se]+nowcost){dis[edge[i].v]=dis[p.se]+nowcost;q.push(make_pair(-dis[edge[i].v],edge[i].v));PrePoint[edge[i].v]=p.se;PreEdge[edge[i].v]=i;}}}if(dis[T]>=INF) break;for(int i=0;i<=N;i++) h[i]+=dis[i];long long nowflow=INF;for(int now=T;now!=S;now=PrePoint[now])nowflow=min(nowflow,edge[PreEdge[now]].f);for(int now=T;now!=S;now=PrePoint[now])edge[PreEdge[now]].f-=nowflow,edge[PreEdge[now]^1].f+=nowflow;ansflow+=nowflow;anscost+=nowflow*h[T];}return make_pair(ansflow,anscost);
}
int main()
{N=read(),M=read(),S=read(),T=read();for(int i=1;i<=M;i++){int x=read(),y=read(),f=read(),z=read();AddEdge(x,y,f,z);}Pair ans=Dij();printf("%lld %lld\n",ans.fi,ans.se);return 0;
}