头像

豆浆灬油条


访客:6643

离线:11小时前


分享 网络流2

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

Dinic算法

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

1、当前弧优化

9.png

2号优化 (不知道叫什么名字)

10.png

3号优化

11.png

#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);
        add(a, b, c), add(b, a, 0);
    }

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

    return 0;
}

最大流之上下界可行流

无源汇上下界可行流

首先假设有一个网络流,它满足题目的要求,且满足条件。
$$
1、流量守恒 \\
2、c_{low}(u, v) \le f(u, v) \le c_{up}(u, v)
$$
1.png

但是这个网络流不满足一般性质,所以需要进行一些修改,并构建一个新的图。
$$
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)并构建一个新的图
$$
2.png

通过观察发现这个新图因为每条边都减去了容量的下届所以此时的可行流不再满足流量守恒了。所以需要对每个点进行一些操作让它满足流量守恒。
$$
首先记 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的值是对于原网络中的可行流)
$$
4.png
$$
当 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入} 来保证流量守恒 \\
$$
通过操作完之后的图变成了

3.png

此时对这个图进行跑最大流 如果能够跑满流(也就是 每一条 f(S, v) == c(S, v)) 那么就存在了一种可行解。

证明:
$$
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);
        add(b, a, 0, 0);
    }
    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;
}

有源汇上下界最大流

首先我们可以先和上面的题目进行一个转化 然后发现这其中有源点和汇点是不满足流量守恒性质的。所以我们可以通过连一条汇点到源点的边 容量为无穷大。

5.png

然后我们通过上面的转化成一个新图。

6.png

现在我们假设新图中从 超级源点 S 出去的边都能够跑满流。然后我们面临的一个问题是如何求最大流。

首先我们记
$$
f’ 为原图(第一个图)的一个可行流\\
f_{0}’ 为新图(第二个图)的一个可行流 \\
f_{0s->t}’为新图中 s 到 t 的可行流
$$
下图为原图的一个可行流。
$$
f’ = 6
$$
9.png

下图为新图的一个满流。其中
$$
f_{0}’ = 5 \\
f_{0s->t}’ = f(t, s) = 4
$$
7.png

然后我们在新图的当前的残留网络中去掉 超级源点 S 和 超级汇点 T。并且记当前的可行流
$$
f_{s->t}’ 为残留网络的一个可行流 \\
比如下面图的f_{s->t}’= 2
$$
8.png

通过观察可以发现
$$
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}’
$$
10.png
$$
因为 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}’对应
$$
11.png

最后我们要让
$$
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);
        add(a, b, d - c);
        add(b, a, 0);
        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];
        else if(A[i] < 0)   add(i, T, -A[i]), add(T, i, 0);
    }

    add(t, s, inf), add(s, t, 0);

    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);
        add(a, b, d - c), add(b, a, 0);
        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];
        else if(A[i] < 0)   add(i, T, -A[i]), add(T, i, 0);
    }
    add(t, s, inf), add(s, t, 0);

    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);
        add(S, x, inf), add(x, S, 0);
    }
    for(int i = 1; i <= tc; i ++ ){
        int x;
        scanf("%d", &x);
        add(x, T, inf), add(T, x, 0);
    }
    for(int i = 1; i <= m; i ++ ){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), add(b, a, 0);
    }

    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 ++ ;
        add(a, b, c), add(b, a, 0);
    }

    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 ++ ;
        add(a, b, c), add(b, a, 0);
    }

    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;
}


活动打卡代码 AcWing 2234. 多源汇最大流

#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);
        add(S, x, inf), add(x, S, 0);
    }
    for(int i = 1; i <= tc; i ++ ){
        int x;
        scanf("%d", &x);
        add(x, T, inf), add(T, x, 0);
    }
    for(int i = 1; i <= m; i ++ ){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), add(b, a, 0);
    }

    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);
        add(a, b, d - c), add(b, a, 0);
        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];
        else if(A[i] < 0)   add(i, T, -A[i]), add(T, i, 0);
    }
    add(t, s, inf), add(s, t, 0);

    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);
        add(a, b, d - c);
        add(b, a, 0);
        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];
        else if(A[i] < 0)   add(i, T, -A[i]), add(T, i, 0);
    }

    add(t, s, inf), add(s, t, 0);

    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);
        add(b, a, 0, 0);
    }
    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;
}


分享 网络流1

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

网络流的基本概念

1.1流网络,不考虑反向边

在一张有向图中 G = (V, E) 中有一个源点 S 和一个汇点 T。

源点 S 有无限多的水流可以向外流出,汇点 T 可以接受无限多的水流。

其中对于每一条有向边有一个边权代表这条有向边最大可以流过的流量(用 c(u, v) 来表示)。

1.png

1.2 可行流,不考虑反向边

对于可行流用 f 来表示,f 指的是对于一整张有向图而言,指定有向图中每条有向边流过多少流量。f(u, v) 指的是从 u 到 v 的一条有向边的可行流。

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}
$$

2.png

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

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

3.png

1.2.3 最大流是指最大可行流

1.3 残留网络,考虑反向边

残留网络指的是在原网络中指定了可行流之后对应的一个网络流,原网络的一个可行流对应一个残留网络。

其中残留网络的点包含原网络中的所有点 V 、边包含了原网络中的边 E 和其一一对应的反向边 RE。

残留网络的每条边的边权
$$
\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) 是原网络的一条反向边)
$$
其中上图的可行流 f 对应的残留网络为

4.png

1.3.1残留网络的可行流f’ + 原图的可行流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}
$$
5.png

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

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 |
$$

结论 残留网络中的任何一个 f’ ,|f’|大于0,都可以更新原网络的可行流。

1.4 增广路径

增广路径指的是在残留网络中有一条路径从源点到汇点,其中的每一条边的残留容量都大于 0 。

1.5 割

1.5.1 割的定义

将原网络中的 V 分成 2 个子集 S 和 T 。且满足 割 的选择有很多种
$$
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]
$$

6.png

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]
$$

7.png

性质:
$$
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 最大流最小割定理

​ 对于一个网络流而言

(1) 可行流f是最大流
(2) 可行流f的残留网络中不存在增广路
(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

8.png
$$
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);
        add(a, b, c), add(b, a, 0);
    }

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

    return 0;
}

Dinic算法

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

1、当前弧优化

9.png

2号优化 (不知道叫什么名字)

10.png

3号优化

11.png

#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);
        add(a, b, c), add(b, a, 0);
    }

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

    return 0;
}


活动打卡代码 AcWing 2179. 圆桌问题

#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);
        add(S, i, x);
        add(i, S, 0);
        res += x;
    }
    for(int i = 1; i <= n; i ++ ){
        int x;
        scanf("%d", &x);
        add(m + i, T, x);
        add(T, m + i, 0);
    }
    for(int i = 1; i <= m; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            add(i, m + j, 1);
            add(m + j, i, 0);
        }
    }

    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;
}


活动打卡代码 AcWing 2171. EK求最大流

#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);
        add(a, b, c), add(b, a, 0);
    }

    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 ++ ){
        add(0, i, 1);
        add(i, 0, 0);
    }
    for(int i = n + 1; i <= m; i ++ ){
        add(i, T, 1);
        add(T, i, 0);
    }
    int a, b;
    while(cin >> a >> b){
        if(a == -1 && b == -1)  break;
        add(a, b, 1);
        add(b, a, 0);
    }

    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;
}