题目描述

如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。

输入

第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含四个正整数ui、vi、wi、fi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi），单位流量的费用为fi。

输出

一行，包含两个整数，依次为最大流量和在最大流量情况下的最小费用。

样例输入

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

样例输出

50 280

555555本蒟蒻还不会zkw费用流，就先贴Edmond_Karp+SPFA和Primal_Dual的代码吧。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <vector>
  5 #include <queue>
  6 using namespace std;
  7 
  8 struct edge {
  9     int to,cap,cost,rev;
 10 };
 11 
 12 typedef pair<int,int> P;
 13 const int maxn=5000, maxm=50000, INF=0x7F7F7F7F;
 14 int n,m;
 15 vector <edge> G[maxn+1];
 16 
 17 edge make_edge(int to, int cap, int cost, int rev) {
 18     edge x;
 19     x.to=to, x.cap=cap, x.cost=cost, x.rev=rev;
 20     return x;
 21 }
 22 
 23 void add_edge(int from, int to, int cap, int cost) {
 24     G[from].push_back(make_edge(to,cap,cost,G[to].size()));
 25     G[to].push_back(make_edge(from,0,-cost,G[from].size()-1));
 26 }
 27 
 28 void init(int &s, int &t) {
 29     scanf("%d%d%d%d",&n,&m,&s,&t);
 30     for (int i=1; i<=m; i++) {
 31         int u,v,w,f;
 32         scanf("%d%d%d%d",&u,&v,&w,&f);
 33         add_edge(u,v,w,f);
 34     }
 35 }
 36 
 37 namespace EK_SPFA {
 38     int dis[maxn+1];
 39     int prev[maxn+1];
 40     int pree[maxn+1];
 41 
 42     void bfs(int s) {
 43         bool mark[maxn+1];
 44         memset(dis,0x7F,sizeof(dis));
 45         memset(prev,-1,sizeof(prev));
 46         memset(pree,-1,sizeof(pree));
 47         memset(mark,0,sizeof(mark));
 48         queue <int> q;
 49         dis[s]=0;
 50         q.push(s);
 51         while (!q.empty()) {
 52             int x=q.front();
 53             q.pop();
 54             mark[x]=false;
 55             for (int i=0; i<G[x].size(); i++) {
 56                 edge &e=G[x][i];
 57                 if (e.cap>0&&dis[x]+e.cost<dis[e.to]) {
 58                     dis[e.to]=dis[x]+e.cost;
 59                     prev[e.to]=x;
 60                     pree[e.to]=i;
 61                     if (!mark[e.to]) {
 62                         mark[e.to]=true;
 63                         q.push(e.to);
 64                     }
 65                 }
 66             }
 67         }
 68     }
 69 
 70     P min_cost_max_flow(int s, int t) {
 71         int flow=0, cost=0;
 72         for(;;) {
 73             bfs(s);
 74             if (dis[t]==INF)
 75                 return make_pair(flow,cost);
 76             int d=INF;
 77             for (int i=t; prev[i]!=-1; i=prev[i])
 78                 d=min(d,G[prev[i]][pree[i]].cap);
 79             flow+=d;
 80             cost+=d*dis[t];
 81             for (int i=t; prev[i]!=-1; i=prev[i]) {
 82                 edge &e=G[prev[i]][pree[i]];
 83                 e.cap-=d;
 84                 G[e.to][e.rev].cap+=d;
 85             }
 86         }
 87     }
 88 }
 89 
 90 namespace Primal_Dual {
 91     int dis[maxn+1];
 92     int h[maxn+1];
 93     int prev[maxn+1];
 94     int pree[maxn+1];
 95 
 96     void bfs(int s) {
 97         priority_queue <P, vector<P>, greater<P> > q;
 98         bool vis[maxn+1];
 99         memset(vis,0,sizeof(vis));
100         memset(dis,0x7F,sizeof(dis));
101         memset(prev,-1,sizeof(prev));
102         memset(pree,-1,sizeof(pree));
103         dis[s]=0;
104         q.push(make_pair(0,s));
105         while (!q.empty()) {
106             int val=q.top().first, x=q.top().second;
107             q.pop();
108             if (vis[x]) continue;
109             vis[x]=true;
110             for (int i=0; i<G[x].size(); i++) {
111                 edge &e=G[x][i];
112                 if (e.cap>0&&dis[x]+e.cost+h[x]-h[e.to]<dis[e.to]&&!vis[e.to]) {
113                     dis[e.to]=dis[x]+e.cost+h[x]-h[e.to];
114                     prev[e.to]=x;
115                     pree[e.to]=i;
116                     q.push(make_pair(dis[e.to],e.to));
117                 }
118             }
119         }
120     }
121 
122     P min_cost_max_flow(int s, int t) {
123         int flow=0, cost=0;
124         memset(h,0,sizeof(h));
125         for(;;) {
126             bfs(s);
127             if (dis[t]==INF)
128                 return make_pair(flow,cost);
129             for (int i=1; i<=n; i++)
130                 h[i]+=dis[i];
131             int d=INF;
132             for (int i=t; prev[i]!=-1; i=prev[i])
133                 d=min(d,G[prev[i]][pree[i]].cap);
134             flow+=d;
135             cost+=d*h[t];
136             for (int i=t; prev[i]!=-1; i=prev[i]) {
137                 edge &e=G[prev[i]][pree[i]];
138                 e.cap-=d;
139                 G[e.to][e.rev].cap+=d;
140             }
141         }
142     }
143 }
144 
145 int main() {
146     int s,t;
147     init(s,t);
148     P ans=Primal_Dual::min_cost_max_flow(s,t);
149     printf("%d %d\n",ans.first,ans.second);
150     return 0;
151 }