Eason2009 @ 2022-07-06 17:16:53
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,t,ans,head[205],now[205],to[10005],nex[10005],flow[10005],dis[205],tot;
void add(int u,int v,int w)
{
tot++;
to[tot]=v;
flow[tot]=w;
nex[tot]=head[u];
head[u]=tot;
return;
}
bool bfs()
{
queue<int>q;
memset(dis,0,sizeof(dis));
dis[s]=1;
q.push(s);
now[s]=head[s];
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=nex[i])
{
int v=to[i];
if((!dis[v])&&flow[i])
{
now[v]=head[v];
dis[v]=dis[u]+1;
q.push(v);
if(v==t)
{
return 1;
}
}
}
}
return 0;
}
int dfs(int u,int in)
{
int sum=0;
if(u==t) return in;
for(int i=now[u];i;i=nex[i])
{
now[u]=i;
int v=to[i];
if(dis[v]==dis[u]+1&&flow[i])
{
int k=dfs(v,min(in,flow[i]));
if(k==0) dis[v]=0;
flow[i]-=k;
flow[i^1]+=k;
sum+=k;
in-=k;
}
}
return sum;
}
signed main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,0);
}
while(bfs())
{
ans+=dfs(s,1e18);
}
cout<<ans;
return 0;
}
by a1co0av5ce5az1cz0ap_ @ 2022-07-06 17:21:18
1TLE是什么鬼
by Eason2009 @ 2022-07-06 17:22:19
应该是没有用快读的原因,主要是WA的我很难受
by Maxwell_dcc @ 2022-07-06 17:32:36
@Eason2009 tot要初始化为1
by Eason2009 @ 2022-07-06 17:38:51
@Maxwell_dcc AC啦