图论：网络流最小费用最大流

/*最大流最小费用费用为单位流量的费用在最大流的前提下找最短路径即为最小费用边权为当前边的流量乘以单位流量的费用首先构建一个图用最短路算法来找到源点到各个点的最短距离找到这个数据之后，我们就可以沿着最短路来进行增广，即在最短路中求到一条可行路然后修改其残量，我们可以保证其为最大流中的一部分的最小花费不断的进行增广直到我们找到了全部值，然后得解，这就是将dinic和spfa结合起来的求解最小费用最大流问题的方法spfa使用small label first 优化，用deque实现*/#include <bits/stdc++.h>using namespace std;const int maxm=5e4+10;const int maxn=5e3+10;const int inf = 0x3f3f3f3f;struct edge{int v,next;int c,w;//边最大流量，单位流量的费用}e[maxm<<1];int head[maxn],cnt=0;int dis[maxn];int n,m,s,t;bool vis[maxn];int mincost = 0;void add(int u,int v,int c,int w){e[cnt].v=v;e[cnt].c=c;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt++;}void init(){memset(head,-1,sizeof(head));cnt=0;}bool spfa(int s,int t){for (int i=0;i<maxn;i++) dis[i] = inf;memset(vis,0,sizeof(vis));dis[s] = 0;vis[s] = 1;deque<int> dq;dq.push_front(s);while(!dq.empty()){int u=dq.front();dq.pop_front();vis[u] = 0;for (int i=head[u];~i;i=e[i].next){int v=e[i].v;int c=e[i].c;//边的流量int w=e[i].w;//单位流量的花费——边的权值if(c>0 && dis[v] > dis[u] + w){//当前有残量并且是最短路上的边dis[v]=dis[u]+w;//更新最短路if(!vis[v]){if(!dq.empty() && dis[dq.front()]>dis[v]){//SLF优化，如果v的dis比队列的头dis较小，放入队首dq.push_front(v);}else dq.push_back(v);}}}}return dis[t]!=inf;}int dfs(int u,int flow){//在最短路的基础上在残量网络中找增广路if(u == t) return flow;int delta = flow;vis[u] = true;for (int i=head[u];~i;i=e[i].next){int v=e[i].v,c=e[i].c,w=e[i].w;if(c>0 && !vis[v] && dis[v] == dis[u] + w){//注意vis的初始化，spfa和dfs中都用到了int d=dfs(v,min(c,delta));e[i].c-=d;e[i^1].c+=d;delta-=d;mincost+=w*d;if(delta == 0) break;}}vis[u] = false;return flow-delta;}void dinic(int s){int maxflow = 0;while(spfa(s,t)){memset(vis,0,sizeof(vis));maxflow+=dfs(s,inf);}printf(\"%d %d\\n\",maxflow,mincost);}int main(){init();scanf(\"%d%d%d%d\",&n,&m,&s,&t);for (int i=1;i<=m;i++){int u,v,c,w;scanf(\"%d%d%d%d\",&u,&v,&c,&w);add(u,v,c,w);add(v,u,0,-w);//反向边的容量为0，单位费用为-w}dinic(s);return 0;}