寻逍遥2006 @ 2021-08-07 17:10:06
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,i,a,b;
long long ans;
int w[210][210],de[201],q[201],top,rea;
bool bfs()
{
memset(de,0,sizeof(de));
top=rea=1;
q[1]=s;
de[s]=1;
while(top<=rea)
{
for(i=1;i<=n;i++)
{
if(de[i]==0&&w[q[top]][i]!=0)
{
de[i]=de[q[top]]+1;
q[rea+1]=i;
rea++;
}
}
top++;
}
return de[t];
}
int dfs(int a,int minn)
{
if(a==t)
{
ans+=minn;
return minn;
}
else
{
int j,ret=0,g;
for(j=1;j<=n;j++)
{
if(ret==minn) break;
if(w[a][j]!=0&&de[j]==de[a]+1)
{
g=dfs(j,min(minn-ret,w[a][j]));
w[a][j]-=g;
w[j][a]+=g;
ret+=g;
}
}
return ret;
}
}
int main()
{
freopen("P3376_8.in","r",stdin);
cin>>n>>m>>s>>t;
for(i=0;i<m;i++)
{
cin>>a>>b;
cin>>w[a][b];
}
while(bfs())
dfs(s,0x7fffffff);
cout<<ans;
return 0;
}
by Jr_Zlw @ 2021-08-07 17:56:45
大概是输入的边权可能为0?
by spdarkle @ 2021-08-07 18:07:06
是WA还是TLE?
by spdarkle @ 2021-08-07 18:09:40
容量好像没有0的,不然我的ISAP也没法过
by mofianger @ 2021-08-12 15:29:27
这道题有重边,您的cin>>w[a][b]应该改成 w[a][b] += ...@寻逍遥2006