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
90
91
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int inf = 1e9+5;
const int maxn = 5005;
const int maxm = 1e5+5;
struct Edge {
int v,c,flow,cost,next;
} edge[maxm];
int n,m,source,sink;
int tot;
int head[maxn],dist[maxn],pre[maxm];
bool vis[maxn];
void addedge(int u,int v,int c,int cost) {
edge[tot].v = v; edge[tot].c = c;
edge[tot].cost = cost; edge[tot].flow = 0;
edge[tot].next = head[u]; head[u] = tot++;
edge[tot].v = u; edge[tot].c = 0;
edge[tot].cost = -cost; edge[tot].flow = 0;
edge[tot].next = head[v]; head[v] = tot++;
}
bool spfa(int source,int sink) {
queue<int> que;
memset(dist,inf,sizeof dist);
memset(vis , 0, sizeof vis);
memset(pre ,-1, sizeof pre);
dist[source] = 0;
vis[source] = 1;
que.push(source);
while (!que.empty()) {
int cur = que.front(); que.pop();
vis[cur] = 0;
for (int i=head[cur]; i!=-1; i=edge[i].next) {
int v=edge[i].v;
if (edge[i].c > edge[i].flow && dist[v] > dist[cur]+edge[i].cost) {
dist[v] = dist[cur] + edge[i].cost;
pre[v] = i;
if (!vis[v]) {
vis[v] = 1;
que.push(v);
}
}
}
}
if (pre[sink] == -1)
return 0;
return 1;
}
int EK(int source,int sink,int &cost) {
int maxflow = 0;
while (spfa(source,sink)) {
int delta = inf;
int i = pre[sink];
while (i != -1) {
delta = min(delta,edge[i].c-edge[i].flow);
i = pre[edge[i^1].v];
}
i = pre[sink];
while (i != -1) {
edge[i].flow += delta;
edge[i^1].flow -= delta;
cost += (delta * edge[i].cost);
i = pre[edge[i^1].v];
}
maxflow += delta;
}
return maxflow;
}
int main() {
cin >> n >> m >> source >> sink;
memset(head,-1,sizeof head);
int u,v,w,f;
for (int i=1; i<=m; ++i) {
cin >> u >> v >> w >> f;
addedge(u,v,w,f);
}
int cost = 0;
int maxflow = EK(source,sink,cost);
cout << maxflow << " " << cost << endl;
return 0;
}
|