-
Notifications
You must be signed in to change notification settings - Fork 0
/
MCMF.cpp
89 lines (73 loc) · 1.54 KB
/
MCMF.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
const int N = 3100 * 3100;
const ll INF = (ll) 1e10;
struct Edge {
int v, idr;
ll w, c;
};
vector < Edge > gr[N];
int ss = N-2, tt = N-1, pr[N], ide[N];
ll dis[N], phi[N];
bool dijkstra()
{
for( int i = 0; i<N; ++i ) dis[i] = INF;
dis[ss] = 0;
priority_queue< pair<ll,int> > pq;
pq.push({0LL,ss});
while( !pq.empty() )
{
int u = pq.top().second;
ll pd = -pq.top().first;
pq.pop();
if( dis[u] != pd ) continue;
for( int i = 0; i < gr[u].size(); ++i )
{
Edge &e = gr[u][i];
ll nd = pd + e.c + phi[u] - phi[e.v];
if( e.w && nd < dis[e.v] )
{
pr[e.v] = u, ide[e.v] = i;
dis[e.v] = nd;
pq.push( {-nd,e.v} );
}
}
}
for( int i = 0; i < N; ++i ) phi[i] = min( INF, phi[i] + dis[i]);
return dis[tt] != INF;
}
void add ( int u, int v, ll w, ll c )
{
gr[u].push_back( {v, int(gr[v].size()), w, c } );
gr[v].push_back( {u,int(gr[u].size()-1), 0LL, -c } );
}
pair<ll,ll> mfmc()
{
memset( phi, 0, sizeof phi );
ll mf = 0;
ll mc = 0;
while( dijkstra() )
{
ll cf = INF;
for( int v = tt; v != ss; v = pr[v] )
cf = min( cf, gr[pr[v]][ide[v]].w );
if( cf == INF ) return {INF,INF};
for( int v = tt; v != ss; v = pr[v] )
{
auto &e = gr[pr[v]][ide[v]];
auto &er = gr[v][e.idr];
e.w -= cf;
er.w += cf;
mc += cf * e.c;
}
mf += cf;
}
return {mf,mc};
}
int main()
{
return 0;
}