既然网络流的复杂度本来就是玄学，我想着直接用线性规划单纯形算法做了。由于系数矩阵特别稀疏，这里使用了链表进行部分优化，用 next 维护矩阵一行的非零元构成的链表，转轴时只对下标非零的位置进行操作。

但是，在此题使用这种方法还是 TLE 了，只能过 8 个点，评测记录链接。

不知该方法是否可能继续优化至 AC？

代码：

#include <iostream>
#include <limits>
#include <cmath>
using namespace std;

using ll = long long;

constexpr ll INF = numeric_limits<ll>::max();
constexpr ll EPS = 0;
constexpr size_t MAXM = 5405, MAXN = 5005;

struct SimplexTable {
    size_t m, n;
    short int a[MAXM][MAXN];
    short unsigned int next[MAXM][MAXN];
    ll b[MAXM], c[MAXN], v;

    void pivot(size_t l, size_t e)
    {
        ll a_le = a[l][e];
        a[l][e] = 1;
        b[l] /= a_le;
        for (size_t j = next[l][0]; j <= n; j = next[l][j])
        {
            a[l][j] /= a_le;
        }
        ll c_e = c[e];
        c[e] = 0;
        v -= b[l] * c_e;
        for (size_t j = next[l][0]; j <= n; j = next[l][j])
        {
            c[j] -= a[l][j] * c_e;
        }
        for (size_t i = 1; i <= m; i++)
        {
            if (i == l || a[i][e] == 0) continue;
            ll a_ie = a[i][e];
            a[i][e] = 0;
            size_t i_prev = 0;
            for (size_t j = next[l][0]; j <= n; j = next[l][j])
            {
                a[i][j] -= a[l][j] * a_ie;
                while (next[i][i_prev] < j)
                {
                    i_prev = next[i][i_prev];
                }
                if (a[i][j] != 0)
                {
                    if (next[i][i_prev] > j)
                    {
                        next[i][j] = next[i][i_prev];
                        next[i][i_prev] = j;
                    }
                }
                else
                {
                    if (next[i][i_prev] == j)
                    {
                        next[i][i_prev] = next[i][j];
                    }
                }
            }
            b[i] -= b[l] * a_ie;
        }
    }

    void init_next()
    {
        for (size_t i = 1; i <= m; i++)
        {
            size_t prev = 0;
            for (size_t j = 1; j <= n; j++)
            {
                if (a[i][j] != 0)
                {
                    next[i][prev] = j;
                    prev = j;
                }
            }
            next[i][prev] = n + 1;
        }
    }
} table;

ll simplex()
{
    table.init_next();
    size_t m = table.m, n = table.n;
    while (true)
    {
        size_t l = 0, e = 0;
        for (size_t j = 1; j <= n; j++)
        {
            if (table.c[j] > EPS)
            {
                e = j;
                break;
            }
        }
        if (e == 0)
        {
            return table.v;
        }
        double min_ratio = INF;
        for (size_t i = 1; i <= m; i++)
        {
            if (table.a[i][e] > EPS && (double) table.b[i] / table.a[i][e] <= min_ratio)
            {
                min_ratio = (double) table.b[i] / table.a[i][e];
                l = i;
            }
        }
        if (l == 0)
        {
            return INF;
        }
        table.pivot(l, e);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    size_t n, m, s, t;
    cin >> n >> m >> s >> t;

    /*
    For i <= m, the i-th constraint is the flow of edge
    For vertex u, the m + 2 * u - 1 and m + 2 * u are the constraints of vertex.
    */

    table.n = m;
    table.m = m + 2 * n;
    for (size_t i = 1; i <= m; i++)
    {
        size_t u, v;
        ll w;
        cin >> u >> v >> w;
        table.a[i][i] = 1;
        table.b[i] = w;

        if (u != s)
        {
            table.a[m + 2 * u - 1][i] = 1;
            table.a[m + 2 * u][i] = -1;
        }
        else
        {
            table.c[i] = 1;
        }
        
        if (v != t)
        {
            table.a[m + 2 * v - 1][i] = -1;
            table.a[m + 2 * v][i] = 1;
        }
    }

    ll ans = -simplex();

    cout << (long long)round(ans) << '\n';

    return 0;
}