网络流——最小费用最大流模板

#连续最短路算法#

菜鸡自用的板子。

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<queue>
  7 #include<cmath>
  8 using namespace std;
  9 typedef pair<int, int> _pair;
 10 const int maxv= 510;
 11 const int maxe= 21000;
 12 const int inf= 0x3f3f3f3f;
 13 
 14 struct ENode
 15 {
 16     int to;
 17     int cap;
 18     int cost;
 19     int Next;
 20 };
 21 
 22 struct Min_Cost_Max_Flow
 23 {
 24     ENode edegs[maxe];
 25     int Head[maxv], tnt;
 26     int dist[maxv], preV[maxv], preE[maxv];
 27     void init()
 28     {
 29         memset(Head, -1, sizeof(Head));
 30         tnt= -1;
 31     }
 32     void Add_ENode (int _from, int _to, int _cap, int _cost)
 33     {
 34         ++ tnt;
 35         edegs[tnt].to= _to;
 36         edegs[tnt].cap= _cap;
 37         edegs[tnt].cost= _cost;
 38         edegs[tnt].Next= Head[_from];
 39         Head[_from]= tnt;
 40         ++ tnt;
 41         edegs[tnt].to= _from;
 42         edegs[tnt].cap= 0;
 43         edegs[tnt].cost= -_cost;
 44         edegs[tnt].Next= Head[_to];
 45         Head[_to]= tnt;
 46     }
 47 
 48     int Min_cost_max_flow (int s, int t, int maxf, int &flow)
 49     {
 50         int ret= 0;
 51         priority_queue<_pair, vector<_pair>, greater<_pair> > q;
 52 
 53         while (maxf)
 54         {
 55             memset(dist, inf, sizeof(dist));
 56             while (! q.empty()) q.pop();
 57             dist[s]= 0;
 58             q.push(_pair(0, s));
 59 
 60             while (! q.empty())
 61             {
 62                 _pair now= q.top();
 63                 q.pop();
 64                 int u= now.second;
 65                 if (dist[u]< now.first) continue;
 66                 for (int k= Head[u]; k!= -1; k= edegs[k].Next)
 67                 {
 68                     int v= edegs[k].to;
 69                     if (edegs[k].cap> 0&& dist[v]> dist[u]+ edegs[k].cost)
 70                     {
 71                         dist[v]= dist[u]+ edegs[k].cost;
 72                         preV[v]= u;
 73                         preE[v]= k;
 74                         q.push(_pair(dist[v], v));
 75                     }
 76                 }
 77             }
 78 
 79             if (dist[t]== inf) break;
 80             int f= maxf;
 81             for (int i= t; i!= s; i= preV[i])
 82             {
 83                 f= min(f, edegs[preE[i]].cap);
 84             }
 85             for (int i= t; i!= s; i= preV[i])
 86             {
 87                 edegs[preE[i]].cap-= f;
 88                 edegs[preE[i]^ 1].cap+= f;
 89             }
 90             maxf-= f;
 91             flow+= f;
 92             ret+= f* dist[t];
 93         }
 94         return ret;
 95     }
 96 };
 97 
 98 Min_Cost_Max_Flow MCMF;
 99 int num[maxv];
100 int main()
101 {
102     MCMF.init();
103     int s= 0, t= n+ 1;
104     /*建图*/
105     int flow= 0;
106     int ans= MCMF.Min_cost_max_flow(s, t, inf, flow);
107     printf("%d
", ans);
108     return 0;
109 }

View Code

#zkw费用流#

参考网址： https://artofproblemsolving.com/community/c1368h1020435

zkw大佬的改进：①在dfs的时候可以实现多路增广②KM算法节省SPFA时间（然而我这里没有KM，要问为什么，当然是因为我不会了orz）；

but，参考了另外的博客，修修补补又三年~

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <queue>
  6 #include <cmath>
  7 using namespace std;
  8 const int maxv= 200010;
  9 const int maxe= 2000010;
 10 const int INF= 0x3f3f3f3f;
 11 
 12 struct ENode
 13 {
 14     int to;
 15     int c;
 16     int f;
 17     int Next;
 18 };
 19 ENode edegs[maxe];
 20 int Head[maxv], tnt;
 21 void init()
 22 {
 23     memset(Head, -1, sizeof(Head));
 24     tnt= -1;
 25 }
 26 void Add_ENode(int a, int b, int _c, int _f)
 27 {
 28     ++ tnt;
 29     edegs[tnt].to= b;
 30     edegs[tnt].c= _c;
 31     edegs[tnt].f= _f;
 32     edegs[tnt].Next= Head[a];
 33     Head[a]= tnt;
 34     ++ tnt;
 35     edegs[tnt].to= a;
 36     edegs[tnt].c= 0;
 37     edegs[tnt].f= -_f;
 38     edegs[tnt].Next= Head[b];
 39     Head[b]= tnt;
 40 }
 41 
 42 bool vis[maxv];  //访问标记
 43 int dist[maxv];  //每个点的距离标号，其实就是dis[];
 44 inline bool spfa(int s, int t)
 45 {
 46     memset(vis, 0, sizeof(vis));
 47     memset(dist, INF, sizeof(dist));
 48     dist[t]= 0;
 49     vis[t]= 1;//首先SPFA我们维护距离标号的时候要倒着跑，这样可以维护出到终点的最短路径
 50     deque<int> q;
 51     q.push_back(t);//使用了SPFA的SLF优化（SLF可以自行百度或Google）
 52 
 53     while(!q.empty())
 54     {
 55         int u= q.front();
 56         q.pop_front();
 57         for(int k= Head[u]; k!= -1; k=edegs[k].Next)
 58         {
 59             int v= edegs[k].to;
 60             if(edegs[k^1].c&& dist[v]> dist[u]- edegs[k].f)
 61             {
 62                 /*首先c[k^1]是为什么呢，因为我们要保证正流，但是SPFA是倒着跑的，
 63                 所以说我们要求c[k]的对应反向边是正的，这样保证走的方向是正确的*/
 64                 dist[v]= dist[u]- edegs[k].f;
 65                 /*因为已经是倒着的了，我们也可以很清楚明白地知道建边的时候反向边的边权是负的，
 66                 所以减一下就对了（负负得正）*/
 67                 if(!vis[v])
 68                 {
 69                     vis[v]= 1;
 70                     /*SLF优化*/
 71                     if(! q.empty()&& dist[v]< dist[q.front()])q.push_front(v);
 72                     else q.push_back(v);
 73                 }
 74             }
 75         }
 76         vis[u]=0;
 77     }
 78     return dist[s]< INF;//判断起点终点是否连通
 79 }
 80 
 81 int ans; //ans：费用答案
 82 inline int dfs_flow(int now, int c_max, int t)
 83 {
 84     /*这里就是进行増广了,一次dfs进行了多次增广*/
 85     if(now== t)
 86     {
 87         vis[t]=1;
 88         return c_max;
 89     }
 90     int ret= 0, a;
 91     vis[now]=1;
 92 
 93     for(int k=Head[now]; k!= -1; k= edegs[k].Next)
 94     {
 95         int v= edegs[k].to;
 96         if(! vis[v]&& edegs[k].c&& dist[v]== dist[now]- edegs[k].f)
 97         {
 98             /*这个条件就表示这条边可以进行増广*/
 99             a= dfs_flow(v, min(edegs[k].c, c_max- ret), t);
100             if(a)
101             {
102                 /*累加答案，加流等操作都在这了*/
103                 ans+= a* edegs[k].f; /*流过时按流量单位计费*/
104                 //ans+= edegs[k].f; /*流过时费用固定*/
105                 /**注意上面两句指令的区别*/
106                 edegs[k].c-= a;
107                 edegs[k^1].c+= a;
108                 ret+= a;
109             }
110             if(ret== c_max)break;
111         }
112     }
113     return ret;
114 }
115 
116 inline int Min_Cost_Flow(int s, int t)
117 {
118     int flow= 0;
119     ans= 0;  //费用清零
120     while(spfa(s, t))
121     {
122         /*判断起点终点是否连通，不连通说明满流，做完了退出*/
123         vis[t]= 1;
124         while(vis[t])
125         {
126             memset(vis, 0, sizeof vis);
127             flow+= dfs_flow(s, INF, t);//一直増广直到走不到为止（这样也可以省时间哦）
128         }
129     }
130     return flow;//这里返回的是最大流，费用的答案在ans里
131 }
132 int main()
133 {
134     int n, m, s, t;
135     scanf("%d %d %d %d", &n, &m, &s, &t);
136     init();
137     for(int i= 0; i< m; i ++)
138     {
139         int a, b, c, f;
140         scanf("%d%d%d%d", &a, &b, &c, &f);
141         Add_ENode(a, b, c, f);
142     }
143     printf("%d ", Min_Cost_Flow(s, t));
144     printf("%d
", ans);
145     return 0;
146 }

View Code

#DAG图上费用流#

大佬标称模板：

《DAG图上的最小(最大)费用最大流，适用负权边》

  1 //author Forsaken
  2 #define Hello the_cruel_world!
  3 #pragma GCC optimize(2)
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<cstdio>
  7 #include<string>
  8 #include<cstring>
  9 #include<vector>
 10 #include<map>
 11 #include<set>
 12 #include<queue>
 13 #include<stack>
 14 #include<utility>
 15 #include<cmath>
 16 #include<climits>
 17 #include<deque>
 18 #include<functional>
 19 #include<numeric>
 20 #define max(x,y) ((x) > (y) ? (x) : (y))
 21 #define min(x,y) ((x) < (y) ? (x) : (y))
 22 #define lowbit(x) ((x) & (-(x)))
 23 #define FRIN freopen("C:\Users\Administrator.MACHENI-KA32LTP\Desktop\1.in", "r", stdin)
 24 #define FROUT freopen("C:\Users\Administrator.MACHENI-KA32LTP\Desktop\1.out", "w", stdout)
 25 #define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 26 #define outd(x) printf("%d
", x)
 27 #define outld(x) printf("%lld
", x)
 28 #define memset0(arr) memset(arr, 0, sizeof(arr))
 29 #define il inline
 30 using namespace std;
 31 typedef long long ll;
 32 typedef unsigned long long ull;
 33 typedef pair<int, int> pii;
 34 const int maxn = 1e4;
 35 const int INF = 0x7fffffff;
 36 const int mod = 1e9 + 7;
 37 const double eps = 1e-7;
 38 const double Pi = acos(-1.0);
 39 il int read_int()
 40 {
 41     char c;
 42     int ret = 0, sgn = 1;
 43     do
 44     {
 45         c = getchar();
 46     }
 47     while ((c < '0' || c > '9') && c != '-');
 48     if (c == '-') sgn = -1;
 49     else ret = c - '0';
 50     while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
 51     return sgn * ret;
 52 }
 53 il ll read_ll()
 54 {
 55     char c;
 56     ll ret = 0, sgn = 1;
 57     do
 58     {
 59         c = getchar();
 60     }
 61     while ((c < '0' || c > '9') && c != '-');
 62     if (c == '-') sgn = -1;
 63     else ret = c - '0';
 64     while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
 65     return sgn * ret;
 66 }
 67 il ll quick_pow(ll base, ll index)
 68 {
 69     ll res = 1;
 70     while (index)
 71     {
 72         if (index & 1)res = res * base % mod;
 73         base = base * base % mod;
 74         index >>= 1;
 75     }
 76     return res;
 77 }
 78 struct edge
 79 {
 80     int to, capacity, cost, rev;
 81     edge() {}
 82     edge(int to, int _capacity, int _cost, int _rev) :to(to), capacity(_capacity), cost(_cost), rev(_rev) {}
 83 };
 84 struct Min_Cost_Max_Flow
 85 {
 86     int V, H[maxn + 5], dis[maxn + 5], PreV[maxn + 5], PreE[maxn + 5];
 87     vector<edge> G[maxn + 5];
 88     //调用前初始化
 89     void Init(int n)
 90     {
 91         V = n;
 92         for (int i = 0; i <= V; ++i)G[i].clear();
 93     }
 94     //加边
 95     void Add_Edge(int from, int to, int cap, int cost)
 96     {
 97         G[from].push_back(edge(to, cap, cost, G[to].size()));
 98         G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));
 99     }
100     //flow是自己传进去的变量，就是最后的最大流，返回的是最小费用
101     int Min_cost_max_flow(int s, int t, int f, int& flow)
102     {
103         int res = 0;
104         fill(H, H + 1 + V, 0);
105         while (f)
106         {
107             priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > q;
108             fill(dis, dis + 1 + V, INF);
109             dis[s] = 0;
110             q.push(pair<int, int>(0, s));
111             while (!q.empty())
112             {
113                 pair<int, int> now = q.top();
114                 q.pop();
115                 int v = now.second;
116                 if (dis[v] < now.first)continue;
117                 for (int i = 0; i < G[v].size(); ++i)
118                 {
119                     edge& e = G[v][i];
120                     if (e.capacity > 0 && dis[e.to] > dis[v] + e.cost + H[v] - H[e.to])
121                     {
122                         dis[e.to] = dis[v] + e.cost + H[v] - H[e.to];
123                         PreV[e.to] = v;
124                         PreE[e.to] = i;
125                         q.push(pair<int, int>(dis[e.to], e.to));
126                     }
127                 }
128             }
129             if (dis[t] == INF)break;
130             for (int i = 0; i <= V; ++i)H[i] += dis[i];
131             int d = f;
132             for (int v = t; v != s; v = PreV[v])d = min(d, G[PreV[v]][PreE[v]].capacity);
133             f -= d;
134             flow += d;
135             res += d*H[t];
136             for (int v = t; v != s; v = PreV[v])
137             {
138                 edge& e = G[PreV[v]][PreE[v]];
139                 e.capacity -= d;
140                 G[v][e.rev].capacity += d;
141             }
142         }
143         return res;
144     }
145     int Max_cost_max_flow(int s, int t, int f, int& flow)
146     {
147         int res = 0;
148         fill(H, H + 1 + V, 0);
149         while (f)
150         {
151             priority_queue <pair<int, int>> q;
152             fill(dis, dis + 1 + V, -INF);
153             dis[s] = 0;
154             q.push(pair<int, int>(0, s));
155             while (!q.empty())
156             {
157                 pair<int, int> now = q.top();
158                 q.pop();
159                 int v = now.second;
160                 if (dis[v] > now.first)continue;
161                 for (int i = 0; i < G[v].size(); ++i)
162                 {
163                     edge& e = G[v][i];
164                     if (e.capacity > 0 && dis[e.to] < dis[v] + e.cost + H[v] - H[e.to])
165                     {
166                         dis[e.to] = dis[v] + e.cost + H[v] - H[e.to];
167                         PreV[e.to] = v;
168                         PreE[e.to] = i;
169                         q.push(pair<int, int>(dis[e.to], e.to));
170                     }
171                 }
172             }
173             if (dis[t] == -INF)break;
174             for (int i = 0; i <= V; ++i)H[i] += dis[i];
175             int d = f;
176             for (int v = t; v != s; v = PreV[v])d = min(d, G[PreV[v]][PreE[v]].capacity);
177             f -= d;
178             flow += d;
179             res += d*H[t];
180             for (int v = t; v != s; v = PreV[v])
181             {
182                 edge& e = G[PreV[v]][PreE[v]];
183                 e.capacity -= d;
184                 G[v][e.rev].capacity += d;
185             }
186         }
187         return res;
188     }
189 };
190 int n, k, s1, s2, t, flow, arr[maxn + 5];
191 Min_Cost_Max_Flow MCMF;
192 int main()
193 {
194     for (int kase = read_int(); kase > 0; --kase)
195     {
196         n = read_int(), k = read_int();
197         s1 = 0, s2 = 2 * n + 1, t = 2 * n + 2;
198         MCMF.Init(t);
199         MCMF.Add_Edge(s1, s2, k, 0);
200         for (int i = 1; i <= n; ++i)
201         {
202             arr[i] = read_int();
203             MCMF.Add_Edge(i, i + n, 1, arr[i]);
204         }
205         for (int i = 1; i <= n; ++i)
206             for (int j = i + 1; j <= n; ++j)
207             {
208                 if (arr[i] <= arr[j])MCMF.Add_Edge(i + n, j, 1, 0);
209             }
210         for (int i = 1; i <= n; ++i)
211         {
212             MCMF.Add_Edge(s2, i, 1, 0);
213             MCMF.Add_Edge(i + n, t, 1, 0);
214         }
215         cout << MCMF.Max_cost_max_flow(s1, t, INF, flow) << endl;
216     }
217     return 0;
218 }

View Code

end；