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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
| #include <bits/stdc++.h>
#define ll long long
#define db double
#define gc getchar
#define pc putchar
#define pb push_back
using namespace std;
namespace IO
{
template <typename T>
void read(T &x)
{
x = 0; bool f = 0; char c = gc();
while(!isdigit(c)) f |= c == '-', c = gc();
while(isdigit(c)) x = x * 10 + c - '0', c = gc();
if(f) x = -x;
}
template <typename T, typename ...Args>
void read(T &x, Args &...args) {read(x), read(args...);}
template <typename T>
void write(T x)
{
if(x < 0) pc('-'), x = -x;
if(x > 9) write(x / 10);
pc('0' + x % 10);
}
}
using namespace IO;
#define inf 1e18
#define int long long
const int N = 5e4 + 10;
const int M = 5e5;
int n, m, s, t, ss, tt;
int in[N], out[N], sum;
int S, T;
struct Edge {
int v, w, nxt;
} e[M];
int head[N], tot = 1;
void link(int u, int v, int w)
{
e[++tot] = {v, w, head[u]}, head[u] = tot;
e[++tot] = {u, 0, head[v]}, head[v] = tot;
}
queue <int> que;
int dep[N], cur[N];
bool bfs()
{
memset(dep, 0, sizeof(dep));
dep[S] = 1, que.push(S);
while(!que.empty())
{
int u = que.front(); que.pop();
for(int i = head[u], v; i; i = e[i].nxt)
{
if(!e[i].w || dep[v = e[i].v]) continue;
dep[v] = dep[u] + 1;
que.push(v);
}
}
for(int i = 0; i <= n + 2; i++) cur[i] = head[i];
return dep[T];
}
int dfs(int u, int in)
{
if(u == T || !in) return in;
int out = 0;
for(int& i = cur[u], v; i; i = e[i].nxt)
{
if(!e[i].w || dep[v = e[i].v] != dep[u] + 1) continue;
int f = dfs(v, min(in, e[i].w));
e[i].w -= f, e[i^1].w += f;
in -= f, out += f;
if(!in) break;
}
return out;
}
int dinic()
{
int res = 0;
while(bfs()) res += dfs(S, inf);
return res;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
read(n, m, s, t);
for(int i = 1; i <= m; i++)
{
int u, v, low, up; read(u, v, low, up);
link(u, v, up - low);
in[v] += low, out[u] += low;
}
ss = n + 1, tt = n + 2;
for(int i = 1; i <= n; i++)
{
int w = in[i] - out[i];
if(w > 0) link(ss, i, w), sum += w;
if(w < 0) link(i, tt, -w);
}
link(t, s, inf);
S = ss, T = tt; int flow = 0;
while(bfs()) flow += dfs(S, inf);
if(flow != sum) return puts("please go home to sleep"), 0;
flow = e[tot].w;
e[tot].w = e[tot ^ 1].w = 0;
S = t, T = s;
while(bfs()) dep[ss] = dep[tt] = 0, flow -= dfs(S, inf);
write(flow), pc('\n');
return 0;
}
|