//500ms 秒掉洛谷推流问题
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
typedef long long F_type;
const int MAXN = 1.2e3 + 10, INF = 0x3f3f3f3f;
const LL LINF = (LL)INF << 32 | INF;
struct Edge
{
int v, rev;
F_type cap;
Edge(int a, F_type b, int c) : v(a), rev(c), cap(b) {}
};
const F_type maxf=LINF;
F_type exflow[MAXN];
int h[MAXN], cnt[MAXN];
int ht, N, S, T, labelcnt;
vector<Edge> G[MAXN];
vector<int> hq[MAXN];
void clear(int n = MAXN - 1)
{
ht = labelcnt = 0;
for (int i = 0; i <= n; i++)
G[i].clear();
}
void addEdge(int u, int v, F_type cap)
{
G[u].emplace_back(v, cap, G[v].size());
G[v].emplace_back(u, 0, G[u].size() - 1);
}
void update(int u, int newh)
{
++labelcnt;
if (h[u] != N + 1)
--cnt[h[u]];
h[u] = newh;
if (newh == N + 1)
return;
++cnt[ht = newh];
if (exflow[u] > 0)
hq[newh].push_back(u);
}
void globalRelabel()
{
queue<int> q;
for (int i = 0; i <= N + 1; i++)
hq[i].clear();
for (int i = 0; i <= N; i++)
h[i] = N + 1, cnt[i] = 0;
q.push(T);
labelcnt = ht = h[T] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (Edge& e : G[u])
{
if (h[e.v] == N + 1 && G[e.v][e.rev].cap)
{
update(e.v, h[u] + 1);
q.push(e.v);
}
}
ht = h[u];
}
}
void push(int u, Edge& e)
{
if (exflow[e.v] == 0)
hq[h[e.v]].push_back(e.v);
F_type df = min(exflow[u], e.cap);
e.cap -= df;
G[e.v][e.rev].cap += df;
exflow[u] -= df;
exflow[e.v] += df;
}
void discharge(int u)
{
int nxth = N + 1;
for (Edge& e : G[u])
if (e.cap)
{
if (h[u] == h[e.v] + 1)
{
push(u, e);
if (exflow[u] <= 0)
return;
}
else
nxth = min(nxth, h[e.v] + 1);
}
if (cnt[h[u]] > 1)
update(u, nxth);
else
for (; ht >= h[u]; hq[ht--].clear())
{
for (int& j : hq[ht])
update(j, N + 1);
}
}
F_type maxFlow(int s, int t, int n)
{
S = s, T = t, N = n;
memset(exflow, 0, sizeof(exflow));
exflow[S] = maxf;
exflow[T] = -maxf;
globalRelabel();
for (Edge& e : G[S])
push(S, e);
for (; ht >= 0; --ht)
{
while (!hq[ht].empty())
{
int u = hq[ht].back();
hq[ht].pop_back();
discharge(u);
if (labelcnt > (N << 2))
globalRelabel();
}
}
return exflow[T] + maxf;
}
int main()
{
int n, m, s, t, u, v, w;
scanf("%d%d%d%d", &n, &m, &s, &t);
while (m--)
{
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
}
printf("%d", maxFlow(s, t, n));
return 0;
}
风骨散人Chiam
认证博客专家
拖更专业户????
大学僧，考研狗，没上岸，ACM退役选手。名字的含义：希望可以通过努力，能力让家人拥有富足的生活而不是为了生计而到处奔波。“世人慌慌张张，不过是图碎银几两。偏偏这碎银几两，能解世间惆怅，可让父母安康，可护幼子成长 …”Chiam是 -am爱 China中国文章主要内容：Python,C++,C语言,JAVA,C#等语言的教程，ACM题解、模板、算法等，主要是数据结构，数学和图论设计模式，数据库，计算机网络，操作系统，计算机组成原理，Python爬虫、深度学习、机器学学习，计算机系408考研的所有专业课内容。目前还在更新中，博客园，微信公众号同名“风骨散人”，关注公众号可获软件大礼包
