### 你可以参考一下我写的这份代码
```cpp
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
//#define int long long
#define rep(x, a, b) for(int x = (a); x <= (b); ++x)
#define rop(x, a, b) for(int x = (a); x < (b); ++x)
#define per(x, a, b) for(int x = (a); x >= (b); --x)
using namespace std;
typedef long long LL;
typedef double DB;
struct Queue {
int Que[16888], hd, tl, mo;
Queue() {mo = 16383; hd = tl = 0;}
void push(int x) {Que[tl & mo] = x; ++tl;}
void pop() {++hd;}
int front() {return Que[hd & mo];}
int size() {return tl - hd;}
void clear() {hd = tl = 0;}
}Q;
struct graph {
int hd[10005], vr[200005], vl[200005], nt[200005], tt;
int s, t, vs[10005], ds[10005], cr[10005];
void push(int x, int y, int z) {
vr[++tt] = y; vl[tt] = z; nt[tt] = hd[x]; hd[x] = tt;
}
int dfs(int nw, int mf) {
if(nw == t) return mf;
int RS = mf;
for(int &i = cr[nw]; i; i = nt[i]) {
if(vl[i] == 0 || ds[vr[i]] != ds[nw] + 1) continue;
int K = dfs(vr[i], min(RS, vl[i]));
vl[i] -= K;
vl[i ^ 1] += K;
RS -= K;
if(RS == 0) return mf;
}
return mf - RS;
}
bool bfs() {
memset(ds, 0x3f, sizeof(ds));
ds[s] = 0;
Q.push(s);
while(Q.size()) {
int nw = Q.front();
Q.pop();
for(int i = hd[nw]; i; i = nt[i]) {
if(vl[i] == 0 || ds[vr[i]] <= ds[nw] + 1) continue;
ds[vr[i]] = ds[nw] + 1;
Q.push(vr[i]);
}
}
return ds[t] != 0x3f3f3f3f;
}
long long dinic() {
long long F = 0;
int fl = 0;
while(bfs()) {
memcpy(cr, hd, sizeof(hd));
F += dfs(s, 0x3f3f3f3f);
}
return F;
}
}G;
int n, m, x, y, z, w;
signed main() {
scanf("%d%d%d%d", &n, &m, &G.s, &G.t);
G.tt = 1;
rep(i, 1, m) {
scanf("%d%d%d", &x, &y, &z);
G.push(x, y, z);
G.push(y, x, 0);
}
cout << G.dinic();
return 0;
}
by xjsmsms @ 2023-08-15 16:25:17
《萌新》
by xjsmsms @ 2023-08-15 16:25:54
据我所知 80% 以上 Dinic TLE 都是因为当前弧优化假了。
by K8He @ 2023-08-15 16:28:50
@[K8He](/user/306045) 可能吧，本蒟蒻也是第一次写，哪里不对多多指正QWQ
by xjsmsms @ 2023-08-15 16:31:57
@[shinzanmono](/user/610557)
```cpp
for(int p=chead[u];p&&lim;p=graph[p].nxt){
chead[u]=p;
int v=graph[p].to;
if(dep[v]==dep[u]+1&&graph[p].w!=0){
arc=dfs(v,std::min(lim,graph[p].w));
path+=arc,lim-=arc;
graph[p].w-=arc,graph[p^1].w+=arc;
}
}
```
改成：
```cpp
for(int& p=chead[u];p;p=graph[p].nxt){
chead[u]=p;
int v=graph[p].to;
if(dep[v]==dep[u]+1&&graph[p].w!=0){
arc=dfs(v,std::min(lim,graph[p].w));
if(!arc)dep[v]=0;
path+=arc,lim-=arc;
graph[p].w-=arc,graph[p^1].w+=arc;
if(lim<=0)break;
}
}
```
试试
by K8He @ 2023-08-15 16:32:42
@[xuchengkun](/user/723205) 你这个当前弧优化好像挺对的吧
by K8He @ 2023-08-15 16:33:55
```cpp
if(!arc)dep[v]=0;
```
是无用点优化，不是当前弧优化。忘了说了。
by K8He @ 2023-08-15 16:34:58
艹原来楼主早就过了
by K8He @ 2023-08-15 16:36:35
好了，其实是 `dep` 开小了/qd
by shinzanmono @ 2023-08-15 18:57:21