Topic link

Title Description

As the title , Give a network diagram , And its source and sink , Each side knows its maximum flow and unit flow cost , Find out the maximum flow and the minimum cost in the case of maximum flow .

I / O format

Input format :

The first line contains four positive integers N、M、S、T, The number of points 、 The number of directed edges 、 Source point serial number 、 Meeting point number .

Next M Each row contains four positive integers ui、vi、wi、fi, It means the first one i The direction of a bar is from ui set out , arrive vi, The boundary right is wi( That is, the maximum flow rate on this side is wi), The cost per unit flow is fi.

Output format :

a line , Contains two integers , The order is the maximum flow and the minimum cost under the maximum flow .

I/o sample

sample input #1:

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5
sample output #1:

50 280

Expense flow template :

On the premise of maximum flow , Minimum cost . from EK Algorithm expansion .EK Each time bfs Augmentation , hold bfs Change to spfa Find a path that costs the least , Then take this road to optimize the answer .

Can't EK Go get it first EK Write maximum flow , Can't spfa I'll take it spfa The shortest path is looking down .

Then, when building the edge, the cost of the reverse arc is the opposite number of the positive arc , Taking a reverse arc is equivalent to not taking this part of the edge , Then the shortest path part of course needs to eliminate the influence of this section .

AC Code

 #include <bits/stdc++.h>

 using namespace std;
const int MAXN = ;
const int MAXM = ;
const int INF = 0x7FFFFFFF; int n, m, first[MAXN], s, t, sign; int max_flow, min_cost; struct Edge {
int to, cap, cost, next;
} edge[MAXM * ]; inline void init() {
for(int i = ; i <= n; i++ ) {
first[i] = -;
}
sign = ;
} inline void add_edge(int u, int v, int cap, int cost) {
edge[sign].to = v, edge[sign].cap = cap, edge[sign].cost = cost;
edge[sign].next = first[u], first[u] = sign ++;
edge[sign].to = u, edge[sign].cap = , edge[sign].cost = -cost;
edge[sign].next = first[v], first[v] = sign ++;
} int dist[MAXN], inq[MAXN], pre[MAXN], incf[MAXN]; bool spfa(int s, int t) {
for(int i = ; i <= n ; i++ ) {
dist[i] = INF, inq[i] = ;
}
queue<int>que;
que.push(s), inq[s] = , dist[s] = ;
incf[s] = 0x3f3f3f3f;
while(!que.empty()) {
int now = que.front();
que.pop();
inq[now] = ;
for(int i = first[now]; ~i; i = edge[i].next) {
int to = edge[i].to, cap = edge[i].cap, cost = edge[i].cost;
if(cap > && dist[to] > dist[now] + cost) {
dist[to] = dist[now] + cost;
incf[to] = min(incf[now], cap);
pre[to] = i;
if(!inq[to]) {
que.push(to);
inq[to] = ;
}
}
}
}
return dist[t] != INF;
} void update(int s, int t) {
int x = t;
while(x != s) {
int pos = pre[x];
edge[pos].cap -= incf[t];
edge[pos ^ ].cap += incf[t];
x = edge[pos ^ ].to;
}
max_flow += incf[t];
min_cost += dist[t] * incf[t];
} void minCostMaxFlow(int s, int t) {
while(spfa(s, t)) {
update(s, t);
}
} int main()
{
while(~scanf("%d %d %d %d", &n, &m, &s, &t)) {
init();
for(int i = ; i <= m; i++ ) {
int u, v, cap, cost;
scanf("%d %d %d %d", &u, &v, &cap, &cost);
add_edge(u, v, cap, cost);
}
max_flow = min_cost = ;
minCostMaxFlow(s, t);
printf("%d %d\n", max_flow, min_cost);
} return ;
}

Minimum cost and maximum flow (luogu P3381 【 Templates 】 Minimum cost and maximum flow ) More articles about

  1. Luogu P3381 ( The template questions ) Minimum cost and maximum flow

    < Topic link > The main idea of the topic : Given a picture , Given the capacity of the edge and the cost per unit flow , And given the source and sink . Ask you the most flow from the source point to the sink point and the minimum cost in the case of maximum flow . Problem solving analysis : Minimum cost and maximum flow . The following is ...

  2. P3381 [ Templates ] Minimum cost and maximum flow

    EK  + dijkstra (2246ms) Turn on the oxygen (586ms) dijkstra Potential of Can handle negative power  https://www.luogu.org/blog/28007/solution-p3381 ...

  3. Minimum cost and maximum flow Learning notes &amp;&amp;Luogu P3381 【 Templates 】 Minimum cost and maximum flow

    Title Description Give a network diagram , And its source and sink , Each side knows its maximum flow and unit flow cost , Find out the maximum flow and the minimum cost in the case of maximum flow . Topic link Ideas There is no problem with the maximum flow , The key is to keep the cost to a minimum at the same time , therefore , You can put the ...

  4. 【 Luogu p3381】 Templates - Minimum cost and maximum flow ( graph theory )

    subject : Give a network diagram , And its source and sink , Each side knows its maximum flow and unit flow cost , Find out the maximum flow and the minimum cost in the case of maximum flow . solution : stay Dinic On the basis of spfa Algorithm . 1 #include<cst ...

  5. 【BZOJ-2893】 Conquest King Maximum cost, maximum flow ( Minimum flow with lower bounds )

    2893: Conquest King Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 156  Solved: 48[Submit][Status][Discuss] D ...

  6. hdu 2435dinic Algorithm template + The minimum cut property

    hdu2435 Max flow min cut 2014-03-22 Let me just say something source :hdu2435 Max flow min cut Collection I want to contribute 2435 There is a war The question : Here's a digraph for you , One side can be invincible ...

  7. Expm 10_2 Realization Ford-Fulkerson Algorithm , Find the given graph from the source point s To the meeting point t The maximum flow of , And output the minimum cut .

    package org.xiu68.exp.exp10; import java.util.ArrayDeque; import java.util.ArrayList; import java.ut ...

  8. P3376 【 Templates 】 Network maximum flow (luogu)

    P3376 [ Templates ] Network maximum flow (luogu) The largest flow of dinic Algorithm template ( A variety of optimizations have been taken ) Optimize Time inline+ Current arc + Deep fried + Multichannel augmentation 174ms no Current arc 175ms no Deep fried 249 ...

  9. Dinic Maximum flow || Luogu P3376 【 Templates 】 Network maximum flow

    Topic :[ Templates ] Network maximum flow Code : #include<cstring> #include<cstdio> #include<iostream> #define min ...

Random recommendation

  1. ReactJS Taste fresh : Realization tab Page switch and menu bar switch and accordion switch effect , Progress bar effect

    the front about React, I heard about it last year , I don't want to learn , So many things on the front end , After learning a framework, there is a new one to learn

  2. OpenGL Render pipeline

    OpenGL The rendering pipeline has a series of sequential processing stages . Two graphic information data , Vertex data and pixel data , Being processed in the pipeline . Combine , Finally write to the frame buffer . Be careful ,OpenGL You can send the processed data back to your program .( Refer to the gray area ) Open ...

  3. Expand easyui Form validation for ( turn )

    From:http://www.cnblogs.com/gengaixue/archive/2012/07/14/2591054.html easyui Of validatebox() Provides custom validation ...

  4. GLSL Realization Image Filter 【 turn 】

    http://blog.csdn.net/a3070173/archive/2008/11/27/3390477.aspx Image filtering is often used in drawing tools and special effects , Here are some commonly used ...

  5. WebStorm Shortcut collection

    1.webstorm Shortcut key : IntelliJ-Idea Shortcut keys Ctrl+/  or  Ctrl+Shift+/ notes (//  perhaps /*…*/ ) Shift+F6 restructure - rename Ctrl+X Delete row C ...

  6. GBT28181 Medium RTP

    The national standard says h264 Data according to RFC3984 pack , But GB testing tools ——SPVMN, But I do not support RFC3984 The way of packing . No choice but to use it directly RFC3550 The way to pack , It's actually subcontracting , And then add RTP head , For the end of a frame , ...

  7. Scala: Access modifier 、 Operators and loops

    http://blog.csdn.net/pipisorry/article/details/52902234 Scala Access modifier Scala Access modifiers basic and Java The same as , There were :privat ...

  8. how tomcat works Reading notes ( Two )---------- A simple servlet Containers

    app1 ( It is suggested that before reading this chapter , First look at how tomcat works Reading notes ( One )---------- A simple web The server http://blog.csdn.net/dlf123321/arti ...

  9. leecode Question 169 ( Find mode )

    class Solution { public: void quick_sort(vector<int>& nums,int res,int res_end) { )// miss , You can't ...

  10. MyEclipse Next custom ( Support html5 Of )JSP Templates --JSP

    demand : Because of some Mclipse The version was released earlier , So in some versions ( such as Mclipse2014, As for other versions, bloggers don't know if they can create html5 Format JSP page ) Created in JSP When the page is html Part of it is not html5 Format . ...