正式退役了，谨以此文记录三年的竞赛生涯。
字符串
HASH
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ull base = 131;
ull a[10010];
ll prime = 233317;
ull mod = 212370440130137957ll;
ull hashe(string ss) {
ll len = ss.length();
ull anss = 0;
for (ll i = 0; i < len; i ++ )
anss = (anss * base + (ull)ss[i]) % mod + prime;
return anss;
}
int main() {
ll n,ans = 0;
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(ll i = 1; i <= n; i ++ ) {
string str; cin >> str;
a[i] = hashe(str);
}
sort(a + 1, a + n + 1);
for(ll i = 1; i <= n; i ++ ) {
if(a[i] != a[i - 1]) ans ++ ;
}
cout << ans << "\n";
return 0;
}KMP
ll nxt[MAX], nxt1[MAX];
void Solve() {
string pat, txt;
cin >> txt >> pat;
nxt[0] = -1;
for(ll i = 1, j = -1; i < pat.size(); i ++ ) {
while(j != -1 && pat[i] != pat[j + 1]) j = nxt[j];
if(pat[i] == pat[j + 1]) nxt[i] = nxt[ ++ j] ;
if(pat[i + 1] != pat[j + 1] || pat[i] != pat[j]) nxt[i] = j;
}
nxt1[0] = -1;
for(ll i = 1, j = -1; i < pat.size(); i ++ ) {
while(j != -1 && pat[i] != pat[j + 1]) j = nxt1[j];
if(pat[i] == pat[j + 1]) j ++ ;
nxt1[i] = j;
}
for(ll i = 0, j = -1; i < txt.size(); i ++ ) {
while(j != -1 && txt[i] != pat[j + 1]) j = nxt[j];
if(txt[i] == pat[j + 1]) j ++ ;
if(j == pat.size() - 1) cout << i - j + 1 << "\n";
}
for(ll i = 0; i < pat.size(); i ++ ) cout << nxt1[i] + 1 << " ";
}Z函数
ll si = str.size();
vector<ll> z(si + 1);
ll l = 0, r = 0;
for(ll i = 1; i < si; i ++ ) { // 右端点最靠右的匹配段，l记录起点，r记录终点
if(i <= r && z[i - l] < r - i + 1) {
z[i] = z[i - l];
} else {
z[i] = max((ll)0, r - i + 1);
while(i + z[i] < si && str[z[i]] == str[i + z[i]]) ++ z[i];
}
if(i + z[i] - 1 > r) {
l = i; r = i + z[i] - 1;
}
}字典树
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 3e6 + 10; // 定义最大节点数
const int CHARSET_SIZE = 62; // 字符集大小（大写字母26个，小写字母26个，数字10个）
struct Trie {
int nex[MAX][CHARSET_SIZE]; // 存储子节点索引
bool exis[MAX]; // 标记是否有单词在此结束
int cnt; // 当前使用的节点数
int sum[MAX];
void init() {
cnt = 0;
memset(nex, 0, sizeof(nex));
memset(exis, false, sizeof(exis));
memset(sum, 0, sizeof(sum));
}
inline int getnum(char x) { // 映射字符到索引
if (x >= 'A' && x <= 'Z')
return x - 'A';
else if (x >= 'a' && x <= 'z')
return x - 'a' + 26;
else
return x - '0' + 52;
}
inline void insert(const string &s) {
int pos = 0;
for (char c : s) {
int index = getnum(c);
if (!nex[pos][index])
nex[pos][index] = ++ cnt;
pos = nex[pos][index];
sum[pos] ++ ;
}
exis[pos] = true;
}
inline int find(const string &s) {
int pos = 0;
for (char c : s) {
int index = getnum(c);
if (!nex[pos][index])
return false;
pos = nex[pos][index];
}
return sum[pos];
}
}t;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll T; cin >> T;
while (T--) {
t.init();
ll n, q;
cin >> n >> q;
string s;
for (ll i = 0; i < n; i++) {
cin >> s;
// trie.insert(s);
t.insert(s);
}
for (ll i = 0; i < q; i++) {
cin >> s;
// if (trie.find(s)) ans++;
cout << t.find(s) << "\n";
}
}
return 0;
}AC自动机
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
namespace AC {
int trie[maxn][26], cnt; // 字典树
int sum[maxn], fail[maxn]; // 节点字符串的个数，fail指针
int in[maxn], vis[maxn]; // 拓扑排序优化
int num[maxn], ans[maxn]; // 节点指向的字符串序号 出现次数
void init() {
cnt = 0;
for(ll i = 0; i < maxn; i ++ ) {
sum[i] = 0; fail[i] = 0; in[i] = 0; vis[i] = 0; num[i] = 0; ans[i] = 0;
for(ll j = 0; j < 26; j ++ ) trie[i][j] = 0;
}
}
void insert(string pat, ll i) { // 插入
int pos = 0;
for(auto c : pat) {
if(!trie[pos][c - 'a']) trie[pos][c - 'a'] = ++ cnt;
pos = trie[pos][c - 'a'];
}
num[pos] = i;
}
void getfail() { // bfs求失配指针
queue<int> q;
for(ll v = 0; v < 26; v ++ ) { // 预处理第二层，此时所有子节点的fail指向root
int c = trie[0][v];
if(c) {
fail[c] = 0;
q.push(c);
}
}
while(!q.empty()) {
int pos = q.front(); q.pop();
int f = fail[pos]; // 父节点的fail指针
for(ll v = 0; v < 26; v ++ ) {
int c = trie[pos][v];
if(c) {
fail[c] = trie[f][v]; // 如果父节点的fail指针下有当前字符，则指向它，否则指向root，而trie[f][v]默认值为0
in[fail[c]] ++ ; // 拓扑序优化
q.push(c);
} else trie[pos][v] = trie[f][v]; // “造”一个孩子，跳过去匹配
}
}
}
void query(string &txt) {
int pos = 0;
for(auto c : txt) {
pos = trie[pos][c - 'a']; vis[pos] ++ ; ans[num[pos]] = vis[pos];
}
}
void topu() {
queue<int> q;
for(int i = 1; i <= cnt; i ++ ) {
if(in[i] == 0) q.push(i);
}
while(!q.empty()) {
int u = q.front(); q.pop();
ans[num[u]] = vis[u];
int v = fail[u]; in[v] -- ;
vis[v] += vis[u];
if(in[v] == 0) q.push(v);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
AC::init();
ll n; cin >> n;
vector<string> pat(n + 1);
map<string, int> mp;
for(ll i = 1; i <= n; i ++ ) {
cin >> pat[i];
if(mp[pat[i]] == 0) {
AC::insert(pat[i], i);
mp[pat[i]] = i;
}
}
AC::getfail();
string txt; cin >> txt;
AC::query(txt);
AC::topu();
for(ll i = 1; i <= n; i ++ ) cout << AC::ans[mp[pat[i]]] << "\n";
return 0;
}Manacher
vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
k++;
}
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
vector<int> d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
k++;
}
d2[i] = k--;
if (i + k > r) {
l = i - k - 1;
r = i + k;
}
}数据结构
树状数组
ll Lowbit(ll x) { // lowbit是求得区间范围
return x & -x;
}
// 在x位置add上val,从赋值处往上修改 u+lowbit(u)
void Update(ll x,ll val,vector<ll> &c,ll n) {
for(; x <= n; x += Lowbit(x)) c[x] += val;
}
ll Sum(ll x,vector<ll> &c,ll n) {
ll sum = 0;
for(; x > 0; x -= Lowbit(x)) sum += c[x];
return sum;
}
void Solve() {
cin >> n >> m;
vector<ll> c(n + 1,0);
for(ll i = 1; i <= n; i++) {
cin >> arr;
Update(i, arr, c, n);
}
for(ll i = 1;i <= m;i++) {
cin >> f >> x >> y;
if(f == 2) {
cout << Sum(y, c, n) - Sum(x - 1, c, n) << "\n";
}
else Update(x, y, c, n);
}
}单调栈
stack<ll> s;
int main() {
cin >> n;
for(ll i = 1; i <= n; i ++ ) cin >> a[i];
for(ll i = n; i >= 1; i -- ) {
while(!s.empty() && a[s.top()] <= a[i]) s.pop();
f[i] = (s.empty() ? 0 : s.top());
s.push(i);
}
for(ll i = 1; i <= n; i ++ ) cout << f[i] << " ";
return 0;
}最小生成树
// Prim
#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
il int read()
{
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}//快读，不理解的同学用cin代替即可
#define inf 123456789
#define maxn 5005
#define maxm 200005
struct edge
{
int v,w,next;
}e[maxm<<1];
//注意是无向图，开两倍数组
int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans;
//已经加入最小生成树的的点到没有加入的点的最短距离，比如说1和2号节点已经加入了最小生成树，那么dis[3]就等于min(1->3,2->3)
bool vis[maxn];
//链式前向星加边
il void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
//读入数据
il void init()
{
n=read(),m=read();
for(re int i=1,u,v,w;i<=m;++i)
{
u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
}
il int prim()
{
//先把dis数组附为极大值
for(re int i=2;i<=n;++i)
{
dis[i]=inf;
}
//这里要注意重边，所以要用到min
for(re int i=head[1];i;i=e[i].next)
{
dis[e[i].v]=min(dis[e[i].v],e[i].w);
}
while(++tot<n)//最小生成树边数等于点数-1
{
re int minn=inf;//把minn置为极大值
vis[now]=1;//标记点已经走过
//枚举每一个没有使用的点
//找出最小值作为新边
//注意这里不是枚举now点的所有连边，而是1~n
for(re int i=1;i<=n;++i)
{
if(!vis[i]&&minn>dis[i])
{
minn=dis[i];
now=i;
}
}
ans+=minn;
//枚举now的所有连边，更新dis数组
for(re int i=head[now];i;i=e[i].next)
{
re int v=e[i].v;
if(dis[v]>e[i].w&&!vis[v])
{
dis[v]=e[i].w;
}
}
}
return ans;
}
int main()
{
init();
printf("%d",prim());
return 0;
}// Kruskal
ll n, m;
struct edge {
ll x, y, z;
}e[M];
bool cmp(edge u, edge v) {
return u.z < v.z;
}
ll fa[N];
void init() {
for(ll i = 1; i <= n; i ++ ) fa[i] = i;
}
ll find(ll x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void Kruskal() {
ll ans = 0, cnt = 0;
sort(e + 1, e + m + 1, cmp); init();
for(ll i = 1; i <= m; i ++ ) {
ll x = e[i].x, y = e[i].y, z = e[i].z;
ll fx = find(x), fy = find(y);
if(fx == fy) continue;
fa[fx] = fy;
ans += z; cnt ++ ;
}
if(cnt < n - 1) cout << "orz" << "\n";
else cout << ans << "\n";
}
void Solve() {
cin >> n >> m;
for(ll i = 1; i <= m; i ++ ) {
ll x, y, z;
cin >> x >> y >> z;
e[i].x = x; e[i].y = y; e[i].z = z;
}
Kruskal();
}线段树
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 5e5 + 10;
ll n, m, l, x, y, k;
ll a[MAX];
ll ans;
struct segment_tree {
struct Tree {
ll l, r;
ll sum;
ll lazy;
} tr[MAX * 4];
void build(ll i, ll l, ll r) {
tr[i] = {l, r, 0, 0};
if (l == r) {
tr[i].sum = a[l];
return;
}
ll mid = (l + r) >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
tr[i].sum = tr[i << 1].sum + tr[i << 1 | 1].sum;
}
void pushdown(ll i) {
if (tr[i].lazy) {
tr[i << 1].sum += tr[i].lazy * (tr[i << 1].r - tr[i << 1].l + 1);
tr[i << 1 | 1].sum += tr[i].lazy * (tr[i << 1 | 1].r - tr[i << 1 | 1].l + 1);
tr[i << 1].lazy += tr[i].lazy;
tr[i << 1 | 1].lazy += tr[i].lazy;
tr[i].lazy = 0;
}
}
void add(ll i, ll pos, ll k) { // 单点修改
if (tr[i].l == tr[i].r) {
tr[i].sum += k;
return;
}
pushdown(i);
ll mid = (tr[i].l + tr[i].r) >> 1;
if (pos <= mid) add(i << 1, pos, k);
else add(i << 1 | 1, pos, k);
tr[i].sum = tr[i << 1].sum + tr[i << 1 | 1].sum;
}
void modify(ll i, ll l, ll r, ll k) { // 区间修改
if (tr[i].l >= l && tr[i].r <= r) {
tr[i].sum += k * (tr[i].r - tr[i].l + 1);
tr[i].lazy += k;
return;
}
pushdown(i);
ll mid = (tr[i].l + tr[i].r) >> 1;
if (l <= mid) modify(i << 1, l, r, k);
if (r > mid) modify(i << 1 | 1, l, r, k);
tr[i].sum = tr[i << 1].sum + tr[i << 1 | 1].sum;
}
ll search(ll i, ll l, ll r) { // 区间查询
if (tr[i].l >= l && tr[i].r <= r) return tr[i].sum;
pushdown(i);
ll mid = (tr[i].l + tr[i].r) >> 1;
ll sum = 0;
if (l <= mid) sum += search(i << 1, l, r);
if (r > mid) sum += search(i << 1 | 1, l, r);
return sum;
}
ll query(ll i, ll pos) { // 单点查询
if (tr[i].l == tr[i].r) return tr[i].sum;
pushdown(i);
ll mid = (tr[i].l + tr[i].r) >> 1;
if (pos <= mid) return query(i << 1, pos);
else return query(i << 1 | 1, pos);
}
} ST;
int main() {
ll t = 1;
while (t--) {
cin >> n >> m;
for (ll i = 1; i <= n; i++) cin >> a[i];
ST.build(1, 1, n);
for (ll i = 1; i <= m; i++) {
cin >> l;
if(l == 1) {
cin >> x >> k;
ST.add(1, x, k);
} else if (l == 2) {
cin >> x >> y >> k;
ST.modify(1, x, y, k);
} else if (l == 3) {
cin >> x;
cout << ST.query(1, x) << "\n";
} else if (l == 4) {
cin >> x >> y;
cout << ST.search(1, x, y) << "\n";
}
}
}
return 0;
}Tarjan
ll n, m;
ll dfn[N], dfn_maxx;//表示这个点在dfs时是第几个被搜到的
ll low[N];//表示这个点以及其子孙节点连的所有点中dfn最小的值
stack<ll> st;
ll id[N], id_maxx;//标记这个点位于的强连通分量
ll num[N];// 这个强连通分量中的点的数量
ll out[N];//每个强连通分量的出度
ll vis[N];//标记是否在栈中
ll head[N];//每个点连接的第一条边的索引
struct edge {//链式向前星记录的是一个点连接的所有边
ll to;//目标节点
ll nxt;//下一条边的索引
}e[M];
ll cnt;//边的总数，从1开始计数
void add_edge(ll u, ll v) {
cnt ++;
e[cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
void tarjan(ll u) {
low[u] = dfn[u] = ++ dfn_maxx;
vis[u] = 1;
st.push(u);
for(ll i = head[u]; i; i = e[i].nxt) {
ll v = e[i].to;
if(dfn[v] != 0) {
if(vis[v]) low[u] = min(low[u], dfn[v]);
}
else {
tarjan(v);
low[u] = min(low[u], low[v]);
}
}
//找到一个强连通分量的头节点
if(dfn[u] == low[u]) {
id[u] = ++ id_maxx;
num[id_maxx] ++ ;
vis[u] = 0;
while(st.top() != u) {
ll v = st.top(); st.pop();
vis[v] = 0;
id[v] = id_maxx;
num[id_maxx] ++ ;
}
st.pop();
}
}
void Solve() {
cin >> n >> m;
for(ll i = 1; i <= m; i ++ ) {
ll u, v;
cin >> u >> v;
add_edge(u, v);
}
//tarjan找强连通分量
for(ll i = 1; i <= n; i ++ ) {
if(!dfn[i]) tarjan(i);
}
//计算强连通分量的出度
for(ll i = 1; i <= n; i ++ ) {
for(ll j = head[i]; j; j = e[j].nxt) {
if(id[i] != id[e[j].to]) out[id[i]] ++ ;
}
}
ll summ = 0;// 统计强连通分量的数量
ll ans;
for(ll i = 1; i <= id_maxx; i ++ ) {
if(out[i] == 0) {summ ++ ; ans = num[i];}
}
if(summ == 1) cout << ans << "\n";
else cout << "0" << "\n";
}数学
排列组合
//费马小定理求逆元(质数)
const LL maxn(5050);
LL Jc[maxn];
void calJc() //求maxn以内的数的阶乘
{
Jc[0] = Jc[1] = 1;
for(LL i = 2; i < maxn; i++)
Jc[i] = Jc[i - 1] * i % q;
}
LL pow(LL a, LL n, LL p) //快速幂 a^n % p
{
LL ans = 1;
while(n)
{
if(n & 1) ans = ans * a % q;
a = a * a % q;
n >>= 1;
}
return ans;
}
LL niYuan(LL a, LL b) //费马小定理求逆元
{
return pow(a, b - 2, b);
}
LL CC(LL a, LL b) //计算C(a, b)
{
if(a < b) return 0;
return Jc[a] * niYuan(Jc[b], q) % q
* niYuan(Jc[a - b], q) % q;
}
// 暴力求组合数
vector<vector<int>> comb(maxn + 1, vector<int>(maxn + 1, 0));
// 计算组合数，取模
void calculate_combinations() {
for (int n = 0; n <= maxn; ++n) {
for (int k = 0; k <= n; ++k) {
if (k == 0 || k == n) {
comb[n][k] = 1; // C(n, 0) = C(n, n) = 1
} else {
comb[n][k] = (comb[n - 1][k - 1] + comb[n - 1][k]) % q; // 递推关系式，取模
}
}
}
}
// 查询组合数，取模
int get_combination(int n, int k) {
if (k > n || k < 0) {
return 0; // 如果 k 超过 n 或者小于 0，则返回 0
}
return comb[n][k];
}卡特兰数
$$ H_n = \frac {\binom{2n}{n}}{n + 1}(n \geq 2) \\ H_n=\left\{ \begin{array}{rcl} \sum_{i = 1}^n H_{i - 1}H_{n - i} & & {n \geq 2}\\ 1 & & {n = 0,1} \end{array} \right. \\ H_n = \frac{H_{n - 1}(4n - 2)}{n + 1} \\ H_n = {\binom{2n}{n}} - {\binom{2n}{n - 1}} $$
SG
void SG() {
for(ll i = 1; i <= 100; i ++ ) {
for(ll j = 1; j <= i; j ++ ) {
set<ll> s;
for(ll k = (i + 1) / 2; k < i; k ++ ) {
s.insert(sg[{k, i - k}]);
}
for(ll k = (j + 1) / 2; k < j; k ++ ) {
s.insert(sg[{k, j - k}]);
}
while(s.find(sg[{i, j}]) != s.end()) {
sg[{i, j}] ++ ;
}
}
}
}图论
LCA(重链剖分)
// P3379 【模板】最近公共祖先（LCA）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 500500;
vector<ll> g[N];
ll fa[N]; // 父节点
ll dep[N]; // 深度
ll top[N]; // 重链头节点
ll sz[N]; // 子树大小
ll son[N]; // 重子节点
void dfs1(ll u) { // 维护子树大小、节点深度、父节点、重子节点
sz[u] = 1;
dep[u] = dep[fa[u]] + 1;
for(auto v : g[u]) {
if(v == fa[u]) continue;
fa[v] = u;
dfs1(v);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(ll u, ll h) { //维护重链头节点
top[u] = h;
if(son[u]) dfs2(son[u], h);
for(auto v : g[u]) {
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
ll LCA(ll u, ll v) {
while(top[u] != top[v]) {
if(dep[top[u]] > dep[top[v]])
u = fa[top[u]];
else
v = fa[top[v]];
}
return dep[u] < dep[v] ? u : v;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll n, m, s; cin >> n >> m >> s;
for(ll i = 1; i < n; i ++ ) {
ll u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(s); dfs2(s, s);
for(ll i = 1; i <= m; i ++ ) {
ll u, v; cin >> u >> v;
cout << LCA(u, v) << "\n";
}
return 0;
}LCA(dfs序 + ST)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6;
vector<ll> g[N];
ll dfn[N]; // dfs时间戳
ll st[N][3]; // st数组，前一个参数为dfn[u], 后一个参数为fa[u]
ll dn; // 时间戳
void dfs(ll u, ll fa) { // 维护时间戳
st[dfn[u] = ++ dn][0] = fa;
for(auto v : g[u]) {
if(v != fa) dfs(v, u);
}
}
ll get(ll x, ll y) { // 求最小的时间戳的节点
return dfn[x] < dfn[y] ? x : y;
}
void ST(ll n) { // 构造st数组
for(ll j = 1; j <= __lg(n); j ++ ) {
for(ll i = 1; i <= n - (1 << j) + 1; i ++ ) {
st[i][j] = get(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
ll LCA(ll u, ll v) {
if(u == v) return u;
if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
ll k = __lg(v - u ++ );
ll d = v - (1 << k) + 1;
return get(st[u][k], st[d][k]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll n, m, s; cin >> n >> m >> s;
for(ll i = 1; i < n; i ++ ) {
ll u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(s, 0); ST(n);
for(ll i = 1; i <= m; i ++ ) {
ll u, v; cin >> u >> v;
cout << LCA(u, v) << "\n";
}
return 0;
}网络流
EK 时间复杂度$O(nm^2)$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1210;
const int inf = 0x3f3f3f3f;
ll graph[MAX][MAX];
ll n, m, st, ed;
ll ans;
ll pre[MAX];
bool vis[MAX];
ll l[MAX];
bool bfs() {
memset(pre, -1, sizeof(pre));
memset(vis, 0, sizeof(vis));
ll hh = 0, tt = 0;
pre[st] = st;
vis[st] = 1;
l[ ++ tt] = st;
while(hh < tt) {
ll pos = l[ ++ hh];
for(ll i = 1; i <= n; i ++ ) {
if(!vis[i] && graph[pos][i] > 0) {
vis[i] = 1;
pre[i] = pos;
if(i == ed) return true;
l[ ++ tt] = i;
}
}
}
return false;
}
void EK() {
while(bfs()) {
ll w = inf;
for(ll i = ed; i != st; i = pre[i]) w = min(w, graph[pre[i]][i]);
for(ll i = ed; i != st; i = pre[i]) {
graph[pre[i]][i] -= w;
graph[i][pre[i]] += w;
}
ans += w;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> st >> ed;
ll x, y, z;
for(ll i = 1; i <= m; i ++ ) {
cin >> x >> y >> z;
if(graph[x][y] == 0) graph[x][y] = z;
else graph[x][y] += z;
}
EK();
cout << ans << "\n";
return 0;
}Dinic 时间复杂度$O(n^2m)$
#include <bits/stdc++.h>
using namespace std;
const long long inf=2005020600;
int n,m,s,t,u,v;
long long w,ans,dis[520010];
int tot=1,now[520010],head[520010];
struct node {
int to,net;
long long val;
} e[520010];
inline void add(int u,int v,long long w) {
e[++tot].to=v;
e[tot].val=w;
e[tot].net=head[u];
head[u]=tot;
e[++tot].to=u;
e[tot].val=0;
e[tot].net=head[v];
head[v]=tot;
}
inline int bfs() { //在惨量网络中构造分层图
for(register int i=1;i<=n;i++) dis[i]=inf;
queue<int> q;
q.push(s);
dis[s]=0;
now[s]=head[s];
while(!q.empty()) {
int x=q.front();
q.pop();
for(register int i=head[x];i;i=e[i].net) {
int v=e[i].to;
if(e[i].val>0&&dis[v]==inf) {
q.push(v);
now[v]=head[v];
dis[v]=dis[x]+1;
if(v==t) return 1;
}
}
}
return 0;
}
inline int dfs(int x,long long sum) { //sum是整条增广路对最大流的贡献
if(x==t) return sum;
long long k,res=0; //k是当前最小的剩余容量
for(register int i=now[x];i&∑i=e[i].net) {
now[x]=i; //当前弧优化
int v=e[i].to;
if(e[i].val>0&&(dis[v]==dis[x]+1)) {
k=dfs(v,min(sum,e[i].val));
if(k==0) dis[v]=inf; //剪枝，去掉增广完毕的点
e[i].val-=k;
e[i^1].val+=k;
res+=k; //res表示经过该点的所有流量和（相当于流出的总量）
sum-=k; //sum表示经过该点的剩余流量
}
}
return res;
}
int main() {
scanf("%d%d%d%d",&n,&m,&s,&t);
for(register int i=1;i<=m;i++) {
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);
}
while(bfs()) {
ans+=dfs(s,inf); //流量守恒（流入=流出）
}
printf("%lld",ans);
return 0;
}