反向边不是这样判断的啊，dfs 函数里面错了。
我的建议是使用链式前向星存图，边的编号从 $0$ 或 $2$ 开始，这样边 $i$ 的反向边的编号就是 $i \oplus 1$ 了。
by 2019zll @ 2023-05-05 19:20:19
当然了，对于这道题，开一个 $n \times n$ 的二维数组存图也是可以的，只不过（如果有）重边就把边权加起来。
by 2019zll @ 2023-05-05 19:22:00
为了以后的方便（比如 $10^5$ 个点的二分图匹配），建议使用链式前向星。
@[li_bai_Delete](/user/757946)
by 2019zll @ 2023-05-05 19:23:09
@[2019zll](/user/297895) 您指出了dfs的错误，但我希望您指出是哪一行，哪一个步骤来具体说明，另外，本人并没有学链式前向星，所以习惯用vector来存图。
by gaolangwen_is_sb @ 2023-05-05 19:41:26
```c++
nbr[x][nxt].w-=val;
nbr[nxt][x].w+=val;
```
这里你错以为是普通二维数组存图了。
@[li_bai_Delete](/user/757946)
by 2019zll @ 2023-05-05 19:55:36
提供我的代码
```c++
#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
int ch=getchar();
num=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
static int ch[20],cnt=0;
if(a==0)putchar('0');
while(a)ch[cnt++]=a%10|48,a/=10;
while(cnt)putchar(ch[--cnt]);
}
template<typename T>
inline T min(const T a,const T b){
return a<b?a:b;
}
typedef long long ll;
const int maxn=10000,maxm=100000;
const ll inf=0x7fffffffffffffff;
int n,m,s,t;
int head[maxn+1],cur[maxn+1],total=1;//total 从 1 而不是 0 开始。
struct Edge{
int to,next,flow;
}e[maxm*2+2];
void add(const int u,const int v,const int w){
e[++total]=Edge{v,head[u],w};//++total
head[u]=total;
}
int dep[maxn+1];
int q[maxn+1],front,tail;
bool bfs(){
memset(dep+1,-1,sizeof(int)*n);
front=1,tail=0;
q[++tail]=s;
dep[s]=0;
while(front<=tail){
const int u=q[front++];
for(int i=head[u];i;i=e[i].next){
const int v=e[i].to;
if(e[i].flow&&dep[v]==-1){
dep[v]=dep[u]+1;
q[++tail]=v;
}
}
}
return dep[t]!=-1;
}
ll dfs(const int u,ll in){
if(u==t)return in;
ll out=0;
for(int&i=cur[u];i;i=e[i].next){
const int v=e[i].to;
if(e[i].flow&&dep[v]==dep[u]+1){
const int res=dfs(v,min(in,(ll)e[i].flow));
in-=res;
out+=res;
e[i].flow-=res;
e[i^1].flow+=res;//反向边就是通过异或 1 实现的。
if(!in)break;
}
}
if(!out)dep[u]=-1;
return out;
}
ll maxflow;
void dinic(){
while(bfs()){
memcpy(cur+1,head+1,sizeof(int)*n);
maxflow+=dfs(s,inf);
}
}
int main(){
read(n),read(m),read(s),read(t);
for(int i=1,u,v,w;i<=m;i++){
read(u),read(v),read(w);
add(u,v,w),add(v,u,0);
}
dinic();
write(maxflow),putchar('\n');
return 0;
}
```
by 2019zll @ 2023-05-05 19:57:37
如果你非要用 vector 存图，就需要对每条边存个编号，更麻烦，不如链式前向星边自带编号，建议你学一下，日子久了自然会背熟的。
by 2019zll @ 2023-05-05 19:59:30
@[2019zll](/user/297895) 谢谢，刚刚自学了链式前向星，我改完之后，发现还是卡死了，请您再帮忙看一看。
```
#include<bits/stdc++.h>
using namespace std;
const int N=205,mx=0x3f3f3f3f;
int n,m,s,t,ans,dis[N],head[N],cnt=1;
struct eg
{
int next,to,w;
}e[N];
struct Node
{
int to,w;
};
vector<Node>nbr[N];
void add(int v,int u,int w)
{
e[++cnt].w=w;
e[cnt].to=u;
e[cnt].next=head[v];
head[v]=cnt;
return ;
}
bool bfs()
{
queue<int>q;
memset(dis,-1,sizeof dis);
int cur=s;
q.push(cur);
dis[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=nbr[cur][i].to,w=nbr[cur][i].w;
if(dis[v]==mx&&w>0)
{
q.push(v);
dis[v]=dis[u]+1;
if(v==t)
return true;
}
}
}
return false;
}
int dfs(int u,int sum)
{
if(u==t)
return sum;
int num=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to,w=e[i].w;
if(dis[u]+1==dis[v]&&w>0)
{
int val=dfs(v,min(sum,w));
e[i].w-=val;
e[i^1].w+=val;
num+=val;
sum-=val;
}
}
return num;
}
int main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int x,y,w;
cin>>x>>y>>w;
add(x,y,w);
add(y,x,0);
}
while(bfs()==true)
{
ans+=dfs(s,mx);
}
cout<<ans;
return 0;
}
```
by gaolangwen_is_sb @ 2023-05-05 20:39:37
好的我看看
by 2019zll @ 2023-05-05 20:41:09
```c++
int v=nbr[cur][i].to,w=nbr[cur][i].w;
```
这里把 cur 改成 u！
by 2019zll @ 2023-05-05 20:42:48