问题

将下面这篇文章中问题的条件修改为流量可以被分割，也就是最大流模型。

样例输入

4 5 1 4
1 2 3
1 3 6
2 3 4
2 4 5
3 4 3

样例输出

8

建模

本题需要在无向图中求给定源点s到汇点t的最大流。

课本上的最大流是有向图，这里需要把无向边都转化为一对方向相反的有向边边，每对中两条边的容量是相等的，流量是互为相反数的，即如果u到v流量是w，则v到u流量自然是是-w。在增流的时候，按照搜索时形成的方向对对应的“顺向的边”进行读取和操作，“反向边”在修改流量时对称地“反向操作”即可，即顺向边增流delta，那么反向边退流delta。每条边可以增加的流量仍然为(c-w)，其中容量c>0。（如果w<0，那么这条有向边最大可增加c+|w|，相当于反向边的方向退流|w|，再给顺向边增流c（最大可以增到满）。）只要保证按照正确的方向直接读取与操作顺向边，在更新流时对称地操作反向边，每条边的w值就会合法，即落在[-c, c]区间。

算法

应用Edmond-Karp算法。主要操作是从s开始BFS、给到达的点标号、到达t后反过来更新流值。如果某次BFS不能达到t，则说明不存在增流路径，则已得到最大流。

具体来说，借助一个队列从s开始BFS，取出队列的首元素作为“基点”，给探到的点进行标记，内容是它的前驱（本次的“基点”），与到达此点时可增加的最大流。标记完成之后将其加入队列，继续标记其它与“基点”关联的点。标记完成之后，再取出队列的首元素作为“基点”，……（重复以上操作。）直到如果某次取出了t，说明找到一条增流路径，增大的流量为t的标记中的流量delta。于是以t为起始点，根据标记迭代找前驱、更新当前点……每次需要更新从前驱到当前点的顺向边（加上delta），再对称地更新从当前点到前驱的反向边（减去delta）。直到当前点为s，这一次增流完成。于是删除所有标记，重新从s开始BFS。重复操作多次之后，某一次队列中不曾取出t队列就空了，这时就不能再进行增流。这时s的邻边的流量和就是最大流。

实现

//  Created by Colin on 2020/05/01.
//  Copyright © 2020 Colin. All rights reserved.
//  https://blog.valderfield.com/archives/32/

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int maxn = 102;

struct Node
{
    int capacity;
    int forward;
};

class Edmond_Karp
{
public:
    Node (*graph)[maxn];
    int n, m, s, t;
    int maxflow;
    
    Edmond_Karp(const int _n, const int _m, const int _s, const int _t, Node (*_g)[maxn]):
        n(_n), m(_m), s(_s), t(_t), graph(_g)
    {
        maxflow = 0;
    }
    
    struct Label
    {
        int pre;
        int delta;
    };
    
    int work()
    {
        while (true)
        {
            bool reached = 0;
            Label label[maxn] = { 0 };
            bool viewed[maxn] = { 0 };
            queue<int> q;
            q.push(s);
            viewed[s] = 1;
            label[s].delta = 0x7ffffff;
            while (!q.empty())  // BFS
            {
                int now = q.front();
                q.pop();
                if (now != t)
                {
                    for (int i = 1; i <= n; i++)
                    {
                        if (!viewed[i] && graph[now][i].capacity > 0 && graph[now][i].forward < graph[now][i].capacity)
                        {
                            viewed[i] = 1;
                            q.push(i);
                            // label
                            label[i].pre = now;
                            label[i].delta = min(label[now].delta, graph[now][i].capacity - graph[now][i].forward);
                        }
                    }
                }//end of if
                else    // now == t
                {
                    reached = 1;
                    int delta = label[t].delta;
                    while (now != s)    // update the flow
                    {
                        int pre = label[now].pre;
                        graph[pre][now].forward += delta;
                        graph[now][pre].forward -= delta;
                        now = pre;
                    }
                    break;
                }
            }// end of while
            if (!reached)
                break;
        }// end of while
        // calculate the max flow
        for (int i = 1; i <= n; i++)
        {
            if (graph[s][i].capacity > 0)
                maxflow += graph[s][i].forward;
        }
        return maxflow;
    }
    
};

int main()
{
    Node graph[maxn][maxn] = { 0 };
    // memset(graph, -0x3f, sizeof(graph));
    int n, m, s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v].capacity = graph[v][u].capacity = w;
    }
    Edmond_Karp ek(n, m, s, t, graph);
    printf("%d\n", ek.work());
    
    return 0;
}