%%% y 总 欢迎大佬来指出错误 谢谢大佬啦

#### Dinic算法

while(){
一次找多条增广路，通过分层图;
更新残留网络
}


#### 3号优化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e4 + 10, M = 2e5 + 10, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, cur[N], d[N], q[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// 找增广路 同时将图变成分层图，方便处理环
int bfs()
{
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
d[S] = 0, q[0] = S, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && d[e[i]] == -1){
d[e[i]] = d[u] + 1;
cur[e[i]] = h[e[i]];
if(e[i] == T)   return 1;
q[++ tt] = e[i];
}
}
}
return 0;
}
// 更新残留网络
int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i; // 当前弧优化
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = -1; // 3号优化，将分层图中的当前点变成 -1 相当于打上标记
w[i] -= k, w[i ^ 1] += k, rest += k;
if(rest == flow)    return flow; // 2号优化
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())    while(flow = dfs(S, inf))   res += flow;
return res;
}

int main()
{
cin >> n >> m >> S >> T;
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i ++ ){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
}

printf("%d\n", dinic());

return 0;
}


### 最大流之上下界可行流

#### 无源汇上下界可行流

$$1、流量守恒 \\ 2、c_{low}(u, v) \le f(u, v) \le c_{up}(u, v)$$

$$c_{low}(u, v) \le f(u, v) \le c_{up}(u, v) \\ => 0 \le f(u, v) - c_{low}(u, v) \le c_{up}(u, v) - c_{low}(u, v) 它满足了我们的一般性质 \\ 令 g(u, c) = f(u, v) - c_{low}(u, v)并构建一个新的图$$

$$首先记 c_{x出} = \sum_{(v \in V)}c_{low}(x, v)[(x, v) \in E] \\ c_{x入} = \sum_{(v \in V)}c_{low}(v, x)[(v, x) \in E] \\ f_{x入} = \sum_{(v \in V)}f(v, x)[(v, x) \in E] (注意这个f的值是对于原网络中的可行流) \\ f_{x出} = \sum_{(v \in V)}f(x, v)[(x, v) \in E] (注意这个f的值是对于原网络中的可行流)$$

$$当 c_{x入} > c_{x出} => f_{x入} - c_{x入} < f_{x出} - c_{x出} \\ 此时就需要建立一个超级源点向当前 x 点连一条边 容量为 c_{x入} - c_{x出} 来保证流量守恒 \\ 当 c_{x入} < c_{x出} => f_{x入} - c_{x入} > f_{x出} - c_{x出} \\ 此时就需要建立一个超级汇点，从当前 x 点连一条边到汇点 容量为 c_{x出} - c_{x入} 来保证流量守恒 \\$$

$$1、容量限制 \\ 对于原图 => c_{low}(u, v) \le f(u, v) \le c_{up}(u, v) \\ 对于新图 => 0 \le f(u, v) - c_{low}(u, v) \le c_{up}(u, v) - c_{low}(u, v)$$

$$2、流量守恒 \\ 因为进行了一系列操作同时又从源点出发的每条边都能跑满流到汇点，这样就满足了流量守恒。$$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 210, M = (10200 + N) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx, l[M];
int n, m, S, T, d[N], cur[N], q[N], A[N];

void add(int a, int b, int c, int d)
{
e[idx] = b, w[idx] = d, l[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = S, d[S] = 1, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
cur[e[i]] = h[e[i]];
d[e[i]] = d[u] + 1;
if(e[i] == T)   return 1;
q[ ++ tt] = e[i];
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i;
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k;
w[i ^ 1] += k;
rest += k;
if(rest == flow)    return flow;
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())
while(flow = dfs(S, inf))    res += flow;
return res;
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
S = 0, T = n + 1;
for(int i = 1; i <= m; i ++ ){
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
A[a] -= c, A[b] += c;
add(a, b, c, d - c);
}
int tot = 0;
for(int i = 1; i <= n; i ++ ){
if(A[i] > 0)    add(S, i, 0, A[i]), add(i, S, 0, 0), tot += A[i];
else if(A[i] < 0)   add(i, T, 0, -A[i]), add(T, i, 0, 0);
}

if(dinic() < tot)   puts("NO");
else{
puts("YES");
for(int i = 0; i < m * 2; i += 2 )
printf("%d\n", w[i ^ 1] + l[i]);
}

return 0;
}


#### 有源汇上下界最大流

$$f’ 为原图(第一个图)的一个可行流\\ f_{0}’ 为新图(第二个图)的一个可行流 \\ f_{0s->t}’为新图中 s 到 t 的可行流$$

$$f’ = 6$$

$$f_{0}’ = 5 \\ f_{0s->t}’ = f(t, s) = 4$$

$$f_{s->t}’ 为残留网络的一个可行流 \\ 比如下面图的f_{s->t}’= 2$$

$$f’ = f_{0s->t}’ + f_{s->t}’(其中S->1->2->T的一条增广路是我们通过操作添加的不是s->t的一个增广路径)$$

$$f’ 可以和 f_{s->t}’一一对应$$

$$f_{0}’ 是和 f’一一对应的$$

$$得到式子|f_{s->t}’ + f_{0}’|\首先它一定满足容量限制 \\ 又因为残留网络中任何s->t的流量都可以通过 t->s 的容量为无穷的边流回去所以此时也满足流量守恒 \\ 因为残留网络中任何s->t的流量都可以通过 t->s 的容量为无穷的边流回去，也就是此时的f_{s->t}’ = 0 \\ 所以 |f_{s->t}’ + f_{0}’| = f_{0}’$$

$$因为 f_{0}’ 可以和 f’一一对应所以|f_{s->t}’ + f_{0}’|可以和f’一一对应 \\ 又因为 f_{0}’是固定的所以f_{s->t} 可以和 f’对应$$

$$记f’‘ = |f_{s->t}’ + f_{0}’| \\ 我们通过在|f_{s->t}’ + f_{0}’|中得到图中减去新图的满流 \\ 得到式子 |f’‘ - f_{0}’| = f_{s->t}’\\ 首先它也一定是满足容量限制的 \\ 同时又因为新图中原先只有超级源点和超级汇点不满足流量守恒 \\ 但是因为减去满流之后 此时超级源点和超级汇点的流量都是0 \\ 所以此时的新图也满足流量守恒。 \\ f’ = |f_{s->t}’ + f_{0}’| = f’‘ \\ |f’ - f_{0}’| = f_{s->t}’\\ 因为满流 f_{0}’ 是一个固定的值所以 f’ 可以和 f_{s->r}’对应$$

$$f’ = f_{0s->t}’ + f_{s->t}’最大也就是f_{s->t}’最大$$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 210, M = (N + 10000) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, d[N], cur[N], q[N], s, t, A[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = S, d[S] = 1, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
d[e[i]] = d[u] + 1;
cur[e[i]] = h[e[i]];
q[++ tt] = e[i];
if(e[i] == T)   return 1;
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i;
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k, w[i ^ 1] += k, rest += k;
if(rest == flow)    return flow;
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())    while(flow = dfs(S, inf))   res += flow;
return res;
}

int main()
{
cin >> n >> m >> s >> t;
memset(h, -1, sizeof h);
S = 0, T = n + 1;
for(int i = 1; i <= m; i ++ ){
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
A[a] -= c, A[b] += c;
}

int tot = 0;
for(int i = 1; i <= n; i ++ ){
if(A[i] > 0)    add(S, i, A[i]), add(i, S, 0), tot += A[i];
}

if(dinic() < tot)  puts("No Solution");
else{
int res = w[idx - 1];
S = s, T = t;
w[idx - 1] = w[idx - 2] = 0;
printf("%d\n", res + dinic());
}

return 0;
}


#### 有源汇上下界最小流

$$f’ = f_{0s->t}’ + f_{s->t}’ \\ 其中 f_{s->t}’ = - f_{t->s}’ \\ f’ = f_{0s->t}’- f_{t->s}’ \\ 要使 f’ 最小也就是 f_{t->s}’ 最大$$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 50010, M = (N + 125010) * 2, inf = 0x3f3f3f3f;

int n, m, S, T, s, t, d[N], cur[N], q[N], A[N];
int h[N], ne[M], e[M], w[M], idx;

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = S, d[S] = 1, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
d[e[i]] = d[u] + 1;
cur[e[i]] = h[e[i]];
q[++ tt] = e[i];
if(e[i] == T)   return 1;
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i;
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k;
w[i ^ 1] += k, rest += k;
if(rest == flow)    return flow;
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())    while(flow = dfs(S, inf))   res += flow;
return res;
}

int main()
{
cin >> n >> m >> s >> t;
memset(h, -1, sizeof h);
S = 0, T = n + 1;
for(int i = 1; i <= m; i ++ ){
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
A[a] -= c, A[b] += c;
}

int tot = 0;
for(int i = 1; i <= n; i ++ ){
if(A[i] > 0)    add(S, i, A[i]), add(i, S, 0), tot += A[i];
}

if(dinic() < tot)   puts("No Solution");
else{
int res = w[idx - 1];
S = t, T = s;
w[idx - 1] = w[idx - 2] = 0;
printf("%d\n", res - dinic());
}

return 0;
}


#### 多源汇最大流

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e4 + 10, M = (N + 1e5 + 10) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, sc, tc, d[N], cur[N], q[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = S, d[S] = 1, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
d[e[i]] = d[u] + 1;
cur[e[i]] = h[e[i]];
q[++ tt] = e[i];
if(e[i] == T)   return 1;
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i;
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k, w[i ^ 1] += k, rest += k;
if(rest == flow)    return flow;
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())    while(flow = dfs(S, inf))   res += flow;
return res;
}

int main()
{
cin >> n >> m >> sc >> tc;
memset(h, -1, sizeof h);
S = 0, T = n + 1;
for(int i = 1; i <= sc; i ++ ){
int x;
scanf("%d", &x);
}
for(int i = 1; i <= tc; i ++ ){
int x;
scanf("%d", &x);
}
for(int i = 1; i <= m; i ++ ){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
}

printf("%d\n", dinic());

return 0;
}


#### 最大流之关键边

$$f(u, v) = c(u, v) \\ 存在 源点S 到 u 的路径其中每条边的f < c(流量小于容量) \\ 存在v到汇点T的路径其中每条边的f<c(流量小于容量)$$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = (N + 5010) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, d[N], cur[N], q[N];
bool vis_s[N], vis_t[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] =c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = S, d[S] = 1, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
d[e[i]] = d[u] + 1;
cur[e[i]] = h[e[i]];
q[ ++ tt] = e[i];
if(e[i] == T)   return 1;
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i;
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k, w[i ^ 1] += k, rest += k;
if(rest == flow)    return flow;
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())    while(flow = dfs(S, inf))   res += flow;
return res;
}

void dfs(int u, bool st[], int t)
{
st[u] = 1;
for(int i = h[u]; ~i; i = ne[i]){
if(w[i ^ t] && !st[e[i]]){
dfs(e[i], st, t);
}
}
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
S = 1, T = n;
for(int i = 1; i <= m; i ++ ){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a ++, b ++ ;
}

dinic();

dfs(S, vis_s, 0);
dfs(T, vis_t, 1);

int res = 0;
for(int i = 0; i < m * 2; i += 2){
if(!w[i] && vis_s[e[i ^ 1]] && vis_t[e[i]])
res ++ ;
}
printf("%d\n", res);

return 0;
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = (N + 5010) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, d[N], cur[N], q[N];
bool vis_s[N], vis_t[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] =c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = S, d[S] = 1, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
d[e[i]] = d[u] + 1;
cur[e[i]] = h[e[i]];
q[ ++ tt] = e[i];
if(e[i] == T)   return 1;
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i;
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k, w[i ^ 1] += k, rest += k;
if(rest == flow)    return flow;
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())    while(flow = dfs(S, inf))   res += flow;
return res;
}

void dfs(int u, bool st[], int t)
{
st[u] = 1;
for(int i = h[u]; ~i; i = ne[i]){
if(w[i ^ t] && !st[e[i]]){
dfs(e[i], st, t);
}
}
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
S = 1, T = n;
for(int i = 1; i <= m; i ++ ){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a ++, b ++ ;
}

dinic();

dfs(S, vis_s, 0);
dfs(T, vis_t, 1);

int res = 0;
for(int i = 0; i < m * 2; i += 2){
if(!w[i] && vis_s[e[i ^ 1]] && vis_t[e[i]])
res ++ ;
}
printf("%d\n", res);

return 0;
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e4 + 10, M = (N + 1e5 + 10) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, sc, tc, d[N], cur[N], q[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = S, d[S] = 1, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
d[e[i]] = d[u] + 1;
cur[e[i]] = h[e[i]];
q[++ tt] = e[i];
if(e[i] == T)   return 1;
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i;
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k, w[i ^ 1] += k, rest += k;
if(rest == flow)    return flow;
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())    while(flow = dfs(S, inf))   res += flow;
return res;
}

int main()
{
cin >> n >> m >> sc >> tc;
memset(h, -1, sizeof h);
S = 0, T = n + 1;
for(int i = 1; i <= sc; i ++ ){
int x;
scanf("%d", &x);
}
for(int i = 1; i <= tc; i ++ ){
int x;
scanf("%d", &x);
}
for(int i = 1; i <= m; i ++ ){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
}

printf("%d\n", dinic());

return 0;
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 50010, M = (N + 125010) * 2, inf = 0x3f3f3f3f;

int n, m, S, T, s, t, d[N], cur[N], q[N], A[N];
int h[N], ne[M], e[M], w[M], idx;

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = S, d[S] = 1, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
d[e[i]] = d[u] + 1;
cur[e[i]] = h[e[i]];
q[++ tt] = e[i];
if(e[i] == T)   return 1;
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i;
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k;
w[i ^ 1] += k, rest += k;
if(rest == flow)    return flow;
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())    while(flow = dfs(S, inf))   res += flow;
return res;
}

int main()
{
cin >> n >> m >> s >> t;
memset(h, -1, sizeof h);
S = 0, T = n + 1;
for(int i = 1; i <= m; i ++ ){
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
A[a] -= c, A[b] += c;
}

int tot = 0;
for(int i = 1; i <= n; i ++ ){
if(A[i] > 0)    add(S, i, A[i]), add(i, S, 0), tot += A[i];
}

if(dinic() < tot)   puts("No Solution");
else{
int res = w[idx - 1];
S = t, T = s;
w[idx - 1] = w[idx - 2] = 0;
printf("%d\n", res - dinic());
}

return 0;
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 210, M = (N + 10000) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, d[N], cur[N], q[N], s, t, A[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = S, d[S] = 1, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
d[e[i]] = d[u] + 1;
cur[e[i]] = h[e[i]];
q[++ tt] = e[i];
if(e[i] == T)   return 1;
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i;
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k, w[i ^ 1] += k, rest += k;
if(rest == flow)    return flow;
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())    while(flow = dfs(S, inf))   res += flow;
return res;
}

int main()
{
cin >> n >> m >> s >> t;
memset(h, -1, sizeof h);
S = 0, T = n + 1;
for(int i = 1; i <= m; i ++ ){
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
A[a] -= c, A[b] += c;
}

int tot = 0;
for(int i = 1; i <= n; i ++ ){
if(A[i] > 0)    add(S, i, A[i]), add(i, S, 0), tot += A[i];
}

if(dinic() < tot)  puts("No Solution");
else{
int res = w[idx - 1];
S = s, T = t;
w[idx - 1] = w[idx - 2] = 0;
printf("%d\n", res + dinic());
}

return 0;
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 210, M = (10200 + N) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx, l[M];
int n, m, S, T, d[N], cur[N], q[N], A[N];

void add(int a, int b, int c, int d)
{
e[idx] = b, w[idx] = d, l[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = S, d[S] = 1, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
cur[e[i]] = h[e[i]];
d[e[i]] = d[u] + 1;
if(e[i] == T)   return 1;
q[ ++ tt] = e[i];
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i;
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k;
w[i ^ 1] += k;
rest += k;
if(rest == flow)    return flow;
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())
while(flow = dfs(S, inf))    res += flow;
return res;
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
S = 0, T = n + 1;
for(int i = 1; i <= m; i ++ ){
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
A[a] -= c, A[b] += c;
add(a, b, c, d - c);
}
int tot = 0;
for(int i = 1; i <= n; i ++ ){
if(A[i] > 0)    add(S, i, 0, A[i]), add(i, S, 0, 0), tot += A[i];
else if(A[i] < 0)   add(i, T, 0, -A[i]), add(T, i, 0, 0);
}

if(dinic() < tot)   puts("NO");
else{
puts("YES");
for(int i = 0; i < m * 2; i += 2 )
printf("%d\n", w[i ^ 1] + l[i]);
}

return 0;
}


%%% y 总 蒟蒻刚学网络流想着记点笔记 有问题欢迎指正 谢谢各位大佬啦。

## 网络流的基本概念

### 1.2 可行流，不考虑反向边

#### 1.2.1 f 满足两个条件：容量限制、流量守恒

$$\begin{cases} 1、容量限制 ：0 \le f(u, v) \le c(u, v) \\ 2、流量守恒 ：\forall x \in (V - \{S ,T\}) \sum_{\forall (v, x) \in E} f(v, x) = \sum_{\forall (x, v) \in E} f(x, v) \end{cases}$$

#### 1.2.2 可行流的流量指从源点流出的流量 - 流入源点的流量

$$|f| = \sum_{(s, v) \in E} f(s, v) - \sum_{(v, s) \in E}f(v, s)$$

### 1.3 残留网络，考虑反向边

$$\forall (u, v) \in E 的边权c’(u, v) = c(u, v) - f(u, v) \\ \forall (u, v) \in RE 的边权c’(u, v) = f(v, u)(\forall(v, u) \in E)\\ (这里指的是在原网络E中(v, u)一条边) (在新的残留网络中的c’(u, v) 是原网络的一条反向边)$$

#### 1.3.1残留网络的可行流f’ + 原图的可行流f = 原题的另一个可行流

$$\begin{cases} 1、容量限制 ：0 \le f’(u, v) \le c’(u, v) \\ 2、流量守恒 ：\forall x \in (V - \{S ,T\}) \sum_{\forall (v, x) \in E} f’(v, x) = \sum_{\forall (x, v) \in E} f’(x, v) \end{cases}$$

f’ + f 需满足
$$容量限制 ：\forall (u, v) \in E 的边权c’(u, v) = c(u, v) - f(u, v) \\ \forall(u, v) \in E \\ 0 \le f’(u, v) \le c’(u, v) \\ c’(u, v) = c(u, v) - f(u, v) \\ 0 \le f’(u, v) \le (c(u, v) - f(u, v)) \\ 0 \le f’(u, v) + f(u, v) \le c(u, v)$$

$$因为 f 和 f’ 都满足流量守恒 \\ \forall x \in (V - \{S ,T\}) \sum_{\forall (v, x) \in E} f’(v, x) + \sum_{\forall (v, x) \in E} f(v, x) = \sum_{\forall (x, v) \in E} f’(x, v) + \sum_{\forall (x, v) \in E} f(x, v)$$

$$| f’ + f | = | f’ | + | f |$$

### 1.5 割

#### 1.5.1 割的定义

$$S \bigcup T = V , S \bigcap T = \emptyset \\ 同时 源点 \in S ， 汇点 \in T$$

#### 1.5.2 割的容量，不考虑反向边，“最小割”是指容量最小的割。（应该可以类比上面流网络的定义）

$$割的容量c = \sum_{\forall u \in S}\sum_{\forall v \in T} c(u, v) [(u, v) \in E]$$

#### 1.5.3 割的流量，考虑反向边，f(S, T) <= c(S, T) , f(S, T) = |f| => |f| <= c(S, T)（应该可以类比上面可行流的定义)

$$割的流量 f = \sum_{\forall u \in S}\sum_{\forall v \in T}f(u, v)[(u, v) \in E] - \sum_{\forall v \in S}\sum_{\forall u \in T}f(v, u)[(v, u) \in E]$$

$$f(X, Y) = -f(Y, X) \\ f(X, X) = 0 \\ f(Z, X \bigcup Y) = f(Z, X) + f(Z, Y) \\ f(X \bigcup Y, Z) = f(X, Z) + f(Y, Z)$$

$$f(S, V) = f(S, S \bigcup T) = f(S, S) + f(S, T) \\ f(S, S) = 0 \\ => f(S, T) = f(S, V) \\ f(S, V) = f(\{源点\}, V) + f(S - \{源点\}, V) \\ 记 S’ = S - \{源点\} \\ f(S’, V) = \sum_{\forall u \in S’} \sum_{\forall v \in V} f(u, v)[(u, v) \in E] - \sum_{\forall u \in S’}\sum_{\forall v \in V}f(v, u)[(v, u) \in E] \ = \sum_{\forall u \in S’} (\sum_{\forall v \in V} f(u, v)[(u, v) \in E] - \sum_{\forall v \in V}f(v, u)[(v, u) \in E]) \\ (根据可行流的流量守恒性质 (\sum_{\forall v \in V} f(u, v)[(u, v) \in E] - \sum_{\forall v \in V}f(v, u)[(v, u) \in E]) = 0) 也就是 f(S - {源点}, V) = 0 \\ => f(S, T) = f({源点}, S) = |f| \\ 也就是割的流量 = 可行流$$

#### 1.5.6 最大流最小割定理

​ 对于一个网络流而言

##### (3) 存在某个割[S, T]，|f| = c(S, T)

(1) => (2) 反证法

​ 假设 f 是原网络的一个可行流，同时对应的残留网络中仍然存在一个可行流 f’, 因为 |f + f’| = |f| + |f’| > |f| 这个和定义 f 是最大流矛盾了。

(3) => (1)
$$因为 |f| \le c(S, T)\\ 同时 最大流是|f|的其中一个值 所以 最大流 \le c(S, T) \\ |f| \le 最大流 \\ 存在某个割[S, T]，|f| = c(S, T) \geq 最大流 => |f| \geq 最大流 => (1) |f| 是最大流$$
(2) => (3)

Gf 表示原网络中的不存在增广路的残留网络

S ：在 Gf 中从源点出发沿容量大于 0 的边走能走到的所有点

T = V - S

$$f(x, y) = c(x, y) \\ 反证法 => \\ c’(x, y) = c(x, y) - f(x, y) \\ 如果 c’(x, y) > 0 也就是源点能够到y，这和S集合的定义矛盾 \\ c’(x, y) = 0 => f(x, y) = c(x, y)$$

$$f(a, b) = 0 \\ 反证法 => \\ c’(b,a) = f(a, b), 如果f(a, b) > 0 也就是 c(b,a) > 0，和集合S的定义矛盾 => f(a, b) = 0$$

$$|f| = \sum_{\forall u \in S}\sum_{\forall v \in T}f(u, v)[(u, v) \in E] - \sum_{\forall v \in S}\sum_{\forall u \in T}f(v, u)[(v, u) \in E] \\ \sum_{\forall u \in S}\sum_{\forall v \in T}f(u, v)[(u, v) \in E] = \sum_{\forall u \in S}\sum_{\forall v \in T}c(u, v)[(u, v) \in E] = c(S,T)\\ \sum_{\forall v \in S}\sum_{\forall u \in T}f(v, u)[(v, u) \in E] = 0 \\ => |f| = c(S, T)$$

#### 最大流 = 最小割

$$最大流 = 最小割 \\ 因为最小割是 c(S, T) 中的一个值 所以 最大流 \le 最小割 =>最大流 \le 最小割\\ 最小割 \le c(S, T) = |f| \le 最大流 = > 最小割 \le 最大流\\ 所以最大流 = 最小割$$

### EK算法

while(){
找增广路;
更新残留网络
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1010, M = 20010;
const int inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, maxflow, pre[N], incf[N], vis[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

// 找一条增广路
int bfs()
{
memset(vis, 0, sizeof vis);
queue < int > q;
q.push(S);vis[S] = 1;
incf[S] = inf; // 从源点可以有无限量的水流出来
while(q.size()){
int u = q.front();q.pop();
for(int i = h[u]; ~i; i = ne[i]){
if(w[i]){ // 根据增广路的定义 只有当前边的容量大于 0
int v = e[i];
if(vis[v])  continue;
incf[v] = min(w[i], incf[u]);//一条增广路上流过的最大可行流受到每条边的最小容量限制
pre[v] = i; // 记录当前点的前驱
q.push(v), vis[v] = 1;
if(v == T)  return 1;
}
}
}
return 0;
}

// 更新残留网络
void update()
{
int x = T;
while(x != S){
int i = pre[x];
w[i] -= incf[T]; // c(u, v) 的容量减去找到的增广路上的最小容量
w[i ^ 1] += incf[T]; // (u, v)的方向边加上找到的增广路上的最小容量
x = e[i ^ 1];
}
maxflow += incf[T]; // 累加所有增广路的最大可行流
}

int main()
{
cin >> n >> m >> S >> T;
memset(h, -1, sizeof h);

for(int i = 1; i <= m; i ++ ){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
}

while(bfs())    update();
cout << maxflow << endl;

return 0;
}


### Dinic算法

while(){
一次找多条增广路，通过分层图;
更新残留网络
}


#### 3号优化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e4 + 10, M = 2e5 + 10, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, cur[N], d[N], q[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// 找增广路 同时将图变成分层图，方便处理环
int bfs()
{
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
d[S] = 0, q[0] = S, cur[S] = h[S];
while(hh <= tt){
int u = q[hh ++ ];
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && d[e[i]] == -1){
d[e[i]] = d[u] + 1;
cur[e[i]] = h[e[i]];
if(e[i] == T)   return 1;
q[++ tt] = e[i];
}
}
}
return 0;
}
// 更新残留网络
int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = 0, k;
for(int i = cur[u]; ~i; i = ne[i]){
cur[u] = i; // 当前弧优化
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(flow - rest, w[i]));
if(!k)  d[e[i]] = -1; // 3号优化，将分层图中的当前点变成 -1 相当于打上标记
w[i] -= k, w[i ^ 1] += k, rest += k;
if(rest == flow)    return flow; // 2号优化
}
}
return rest;
}

int dinic()
{
int res = 0, flow;
while(bfs())    while(flow = dfs(S, inf))   res += flow;
return res;
}

int main()
{
cin >> n >> m >> S >> T;
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i ++ ){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
}

printf("%d\n", dinic());

return 0;
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 90010;
const int inf = 0x3f3f3f3f;

int h[N], ne[N], e[N], w[N], idx;
int n, m, S, T, d[N], maxflow;

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
queue < int > q;
q.push(S);
memset(d, 0, sizeof d);
d[S] = 1;
while(q.size()){
int u = q.front();q.pop();
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
q.push(e[i]);
d[e[i]] = d[u] + 1;
if(e[i] == T)   return 1;
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = flow, k;
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k;
w[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}

int main()
{
cin >> m >> n;
memset(h, -1, sizeof h);
S = 0, T = n + m + 1;
int res = 0;
for(int i = 1; i <= m; i ++ ){
int x;
scanf("%d", &x);
res += x;
}
for(int i = 1; i <= n; i ++ ){
int x;
scanf("%d", &x);
}
for(int i = 1; i <= m; i ++ ){
for(int j = 1; j <= n; j ++ ){
}
}

int flow;
while(bfs()){
while(flow = dfs(S, inf))   res -= flow;
}

if(res){
puts("0");
return 0;
}
puts("1");
for(int i = 1; i <= m; i ++ ){
int t = h[i];
while(~t){
if(!w[t])   printf("%d ", e[t] - m);
t = ne[t];
}
printf("\n");
}

return 0;
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1010, M = 20010;
const int inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, maxflow, pre[N], incf[N], vis[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(vis, 0, sizeof vis);
queue < int > q;
q.push(S);vis[S] = 1;
incf[S] = inf;
while(q.size()){
int u = q.front();q.pop();
for(int i = h[u]; ~i; i = ne[i]){
if(w[i]){
int v = e[i];
if(vis[v])  continue;
incf[v] = min(w[i], incf[u]);
pre[v] = i;
q.push(v), vis[v] = 1;
if(v == T)  return 1;
}
}
}
return 0;
}

void update()
{
int x = T;
while(x != S){
int i = pre[x];
w[i] -= incf[T];
w[i ^ 1] += incf[T];
x = e[i ^ 1];
}
maxflow += incf[T];
}

int main()
{
cin >> n >> m >> S >> T;
memset(h, -1, sizeof h);

for(int i = 1; i <= m; i ++ ){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
}

while(bfs())    update();
cout << maxflow << endl;

return 0;
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 10010;
const int inf = 0x3f3f3f3f;

int h[N], ne[N], e[N], w[N], idx;
int n, m, d[N], maxflow, S, T;

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
memset(d, 0, sizeof d);
queue < int > q;
q.push(S);
d[S] = 1;
while(q.size()){
int u = q.front();q.pop();
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && !d[e[i]]){
d[e[i]] = d[u] + 1;
q.push(e[i]);
if(e[i] == T)   return 1;
}
}
}
return 0;
}

int dfs(int u, int flow)
{
if(u == T)  return flow;
int rest = flow, k;
for(int i = h[u]; ~i; i = ne[i]){
if(w[i] && d[e[i]] == d[u] + 1){
k = dfs(e[i], min(rest, w[i]));
if(!k)  d[e[i]] = 0;
w[i] -= k;
w[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}

int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;

S = 0, T = m + 1;
for(int i = 1; i <= n; i ++ ){
}
for(int i = n + 1; i <= m; i ++ ){
}
int a, b;
while(cin >> a >> b){
if(a == -1 && b == -1)  break;
}

int flow;
while(bfs()){
while(flow = dfs(S, inf))   maxflow += flow;
}
cout << maxflow << endl;
for(int i = 1; i <= n; i ++ ){
int u = h[i];
while(~u){
if(!w[u] && e[u] != S)   printf("%d %d\n", i, e[u]);
u = ne[u];
}
}

return 0;
}