constructor @ 2018-08-20 22:19:24

by constructor @ 2018-08-20 22:21:24

如果大家觉得ideone上的代码丑的话这里另附：

#include <iostream>
#include <cstdio>
#include <cctype>
#include <list>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
constexpr int maxn = 1200;
constexpr int maxm = 1200000;
constexpr long long inf = numeric_limits<long long>::max();
struct edge
{
    long long u;
    long long v;
    long long cap;
    long long flow;
};
long long e[maxn];//超额容量
long long h[maxn];//高度函数
int S, T, m, n;
list<int> gra[maxn];
vector<edge> G;
template<class T>
void read(T& opr)
{
    opr = 0;
    static char tmp;
    while (isdigit(tmp = getchar()))
    {
        opr = (opr << 1) + (opr << 3) + tmp - '0';
    }
}
void addedge(int u, int v, long long cap)
{
    G.push_back(edge{ u,v,cap,0 });
    G.push_back(edge{ v,u,0,0 });
    int m = G.size();
    gra[u].push_back(m - 2);
    gra[v].push_back(m - 1);
}
void initPreflow()
{
    h[S] = n;
    for (auto i : gra[S])
    {
        G[i].flow = G[i].cap;
        G[i^1].flow = -G[i].cap;
        e[G[i].v] = G[i].cap;
        e[S] -= G[i].cap;
    }
}
void push(int pos)
{
    edge& opr = G[pos];
    long long amt = min(e[opr.u], opr.cap - opr.flow);
    opr.flow += amt;
    G[pos ^ 1].flow -= amt;
    e[opr.u] -= amt;
    e[opr.v] += amt;
}
void relabel(int u)
{
    long long minh = inf;
    for (auto i : gra[u])
    {
        const edge& opr = G[i];
        if(opr.cap!=opr.flow)
            minh = min(minh, h[opr.v]);
    }
    h[u] = 1 + minh;
}
void discharge(int u)
{
    auto iter = gra[u].begin();
    while (e[u]>0)
    {
        if (iter == gra[u].end())
        {
            relabel(u);
            iter = gra[u].begin();
        }
        else if (h[u] == h[G[*iter].v] + 1)
        {
            push(*iter);
            ++iter;
        }
        else ++iter;
    }
}
void solver()
{
    initPreflow();
    list<int> L;
    for (int i = 1; i <= n; i++)
    {
        if (i != S && i != T)
            L.push_back(i);
    }
    auto u = L.begin();
    while (u != L.end())
    {
        long long oldh = h[*u];
        discharge(*u);
        if (h[*u]>oldh)
        {
            int tmp = *u;
            L.erase(u);
            L.push_front(tmp);
            u = L.begin();
        }
        ++u;
    }
}
int main()
{
    read(n);
    read(m);
    read(S);
    read(T);
    for (int i = 1; i <= m; i++)
    {
        static int u, v, cap;
        read(u);
        read(v);
        read(cap);
        addedge(u, v, cap);
    }
    solver();
    cout << e[T] << endl;
    system("pause");
}```

by constructor @ 2018-08-20 22:24:07

评测结果链接貌似附错了，哈哈哈哈

https://www.luogu.org/record/show?rid=9982277