求助,谢谢
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=205;
const int M=10005;
const int INF=0x3f3f3f3f;
struct edge
{
int v;
ll r;
int next;
}es[M];
int n,m,s,t,cnt=1;
int flag[N][N];
int head[N];
queue<int> q;
bool vis[N];
int d[N];
int pre[N];
ll ans;
void addedge(int u,int v,int w)
{
cnt++;
es[cnt].v=v;
es[cnt].r=w;
es[cnt].next=head[u];
head[u]=cnt;
}
bool bfs()
{
memset(d,0x3f,sizeof(d));
q=queue<int>();
d[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i>0;i=es[i].next)
{
int v=es[i].v;
if(es[i].r>0 && d[v]==INF)
{
q.push(v);
pre[v]=i;
d[v]=d[u]+1;
if (v==t) return true;
}
}
}
}
int dfs(int x,ll flow)
{
if(x==t) return flow;
ll res=0,tmp;
for(int i=head[x];i>0&&flow>0;i=es[i].next)
{
int v=es[i].v;
if(es[i].r>0 && d[v]==d[x]+1)
{
tmp=dfs(v,min(flow,es[i].r));
es[i].r-=tmp;
es[i^1].r+=tmp;
res+=tmp;
flow-=tmp;
}
}
return res;
}
int main()
{
int u,v,w;
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
if(!flag[u][v])
{
addedge(u,v,w);
addedge(v,u,0);
flag[u][v]=cnt;
}
else
{
es[flag[u][v]-1].r+=w;
}
}
//Dinic算法
while(bfs())
{
ans+=dfs(s,INF);
}
cout<<ans<<endl;
return 0;
}