#include<bits/stdc++.h>
using namespace std;
int n,tot,m;
const int maxn=1000000;
int first[maxn],nex[maxn],to[maxn],flow[maxn],cap[maxn],d[maxn];
void add(int x,int y,int z)
{
nex[++tot]=first[x];
to[tot]=y;
cap[tot]=z;
flow[tot]=0;
first[x]=tot;
}
bool bfs(int s,int t)
{
memset(d,0,sizeof(d));
queueq;
d[s]=1;//起点入队
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=first[u];i;i=nex[i])
{
int v=to[i];
if(!d[v]&&cap[i]>flow[i])//可增流
{
d[v]=d[u]+1;
q.push(v);
if(v==t) return 1;
}
}
}
return 0;
}
int dfs(int u,int fl,int t)
{
if(u==t) return fl;//到汇点
int rest=fl;
for(int i=first[u];~i&&rest;i=nex[i])
{
int v=to[i];
if(d[v]==d[u]+1&&cap[i]>flow[i])
{
int k=dfs(v,min(rest,cap[i]-flow[i]),t);
if(!k) d[v]=0;
flow[i]+=k;//通向边曾流
flow[i^1]-=k;//反向边减流
rest-=k;
}
}
return fl-rest;
}
int Dinic(int s,int t)
{
int maxflow=0;
while(bfs(s,t))
{
for(int i=1;i<=n;i++)
maxflow+=dfs(s,0x3f,t);
}
return maxflow;
}
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
}
cout<<Dinic(1,n);
return 0;
}
答案不对
nex[++tot]=first[x];
tot没有初始化为0 啊