最小费用最大流
费用流
费用流算法
现在我们想象假如我们有一个流量网络，现在每个边除了流量，现在还有一个单位费用，这条边的费用相当于它的单位费用乘上它的流量，我们要保持最大流的同时，还要保持边权最小，这就是最小费用最大流问题。 因为在一个网络流图中，最大流量只有一个，但是“流法”有很多种，每种不同的流法所经过的边不同因此费用也就不同，所以需要用到最短路算法。 总增广的费用就是最短路总流量
就是把Dinic中的bfs改成spfa,再求最大流的过程中最小费用流也就求出来了。 有许多初始化的地方容易漏易错； flow和dis容易混易错
#include <bits/stdc++.h>
using namespace std ;
const int MAXN = 5000 + 5 , MAXM = 50000 + 5 ;
struct Node {
int next , to , flow , dis ;
} edge[ MAXM << 1 ] ;
int head[ MAXN ] , cnt = -1 , maxflow , mincost ;
int dis[ MAXN ] , flow[ MAXN ] , pre[ MAXN ] , last[ MAXN ] ;
bool inq[ MAXN ] ;
int n , m , s , t ;
inline int read () {
int tot = 0 , f = 1 ;
char c = getchar () ;
while ( c < '0' || c > '9' ) {
if ( c == '-' ) f = -1 ;
c = getchar () ;
}
while ( c >= '0' && c <= '9' ) {
tot = ( tot << 1 ) + ( tot << 3 ) + ( c ^ 48 ) ;
c = getchar () ;
}
return tot * f ;
}
inline void add ( int x , int y , int z1 , int z2 ) {
edge[ ++ cnt ].to = y ;
edge[ cnt ].next = head[ x ] ;
edge[ cnt ].flow = z1 ;
edge[ cnt ].dis = z2 ;
head[ x ] = cnt ;
}
inline bool spfa () {
memset ( dis , 0x3f , sizeof ( dis ) ) ;
memset ( flow , 0x3f , sizeof ( flow ) ) ;
memset ( inq , 0 , sizeof ( inq ) ) ;
queue < int > q ;
q.push( s ) ; inq[ s ] = 1 ; pre[ t ] = -1 ; dis[ s ] = 0 ;
while ( q.size () ) {
int u = q.front () ;
//cout << u << " " ;
q.pop () ;
inq[ u ] = 0 ;
for ( int i = head[ u ] ; ~i ; i = edge[ i ].next ) {
int v = edge[ i ].to ;
if ( edge[ i ].flow && dis[ u ] + edge[ i ].dis < dis[ v ] ) {
dis[ v ] = dis[ u ] + edge[ i ].dis ;
pre[ v ] = u ;
last[ v ] = i ;
flow[ v ] = min ( flow[ u ] , edge[ i ].flow ) ;
if ( !inq[ v ] ) {
q.push( v ) ;
inq[ v ] = 1 ;
}
}
}
}
return pre[ t ] != -1 ;
}
inline void mcmf () {
while ( spfa () ) {
/*for ( int i = 1 ; i <= n ; i ++ ) cout << pre[ i ] << " " ;cout << endl ;
for ( int i = 1 ; i <= n ; i ++ ) cout << last[ i ] << " " ;cout << endl ;
for ( int i = 1 ; i <= n ; i ++ ) cout << flow[ i ] << " " ;cout << endl ;
for ( int i = 1 ; i <= n ; i ++ ) cout << dis[ i ] << " " ;cout << endl ;*/
int u = t ;
maxflow += flow[ t ] ;
mincost += flow[ t ] * dis[ t ] ;
while ( u != s ) {
edge[ last[ u ] ].flow -= flow[ t ] ;
edge[ last[ u ] ^ 1 ].flow += flow[ t ] ;
u = pre[ u ] ;
}
}
}
signed main () {
memset ( head , -1 , sizeof ( head ) ) ;
n = read () ; m = read () ;
s = read () ; t = read () ;
for ( int i = 1 ; i <= m ; i ++ ) {
int x = read () , y = read () , z1 = read () , z2 = read () ;
add ( x , y , z1 , z2 ) ;
add ( y , x , 0 , -z2 ) ;
}
mcmf () ;
printf ( "%d %d\n" , maxflow , mincost ) ;
return 0 ;
}摘自：https://blog.csdn.net/A_Comme_Amour/article/details/79356220