[板子] 最小费用最大流

题目链接

Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
typedef std::pair<int,int> pr;
const int N = 100010,M = 100010,inf = 0x3f3f3f3f;
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
struct MCMF
{
#define _(a,b) memset(a,b,sizeof(a))
int head[N],pre[N],last[N],vis[N],sflow[N],next[M],to[M],cap[M],flow[M],cost[M],s,t,tot;int dis[N],mxf,mnc;std::queue<int> Q;
MCMF(int s,int t){this->s = s;this->t = t;init();}inline void init(){_(head,-1);_(flow,0);tot = -1;mxf = mnc = 0;}
inline void addedge(int u,int v,int w,int c){next[++tot] = head[u];to[tot] = v;cap[tot] = w;cost[tot] = c;head[u] = tot;}
inline void adde(int u,int v,int w,int c){addedge(u,v,w,c);addedge(v,u,0,-c);}
inline int bfs()
{
_(dis,0x3f);_(sflow,0x3f);_(vis,0);
dis[s] = 0;pre[t] = -1;vis[s] = 1;Q.push(s);
while(!Q.empty())
{
int u = Q.front();Q.pop();vis[u] = 0;
for(register int i = head[u],v = to[i];~i;v = to[i = next[i]]) if(cap[i] > flow[i] && dis[v] > dis[u] + cost[i])
{
dis[v] = dis[u] + cost[i];pre[v] = u;last[v] = i;
sflow[v] = std::min(sflow[u],cap[i] - flow[i]);
if(!vis[v]) {vis[v] = 1;Q.push(v);}
}
}
return ~pre[t] ? 1 : 0;
}
inline pr mcmf()
{
while(bfs())
{
mxf += sflow[t];mnc += sflow[t] * dis[t];
int u = t;while(u != s)
{
flow[last[u]] += sflow[t];flow[last[u] ^ 1] -= sflow[t];
u = pre[u];
}
}
return std::make_pair(mxf,mnc);
}
};
int main()
{
int n = getint(),m = getint(),s = getint(),t = getint();MCMF M(s,t);
for(int i = 1,x,y,z,c;i <= m;i++) {x = getint(),y = getint(),z = getint(),c = getint();M.adde(x,y,z,c);}
pr ans = M.mcmf();printf("%d %d",ans.first,ans.second);
return 0;
}