Xqbk @ 2021-07-25 11:36:39
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=5100;
const int INF=0x3f3f3f3f;
long long n,m,s,t,u,v,c;
long long head[MAXN],nxt[MAXN<<2],to[MAXN<<2],cap[MAXN<<2],flo[MAXN<<2],cnt;
bool vis[MAXN];
int dep[MAXN],cur[MAXN];
void addEdge(int u,int v,long long c)
{
cnt++;
nxt[cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
cap[cnt]=c;
flo[cnt]=0;
}
bool bfs(int s,int t)
{
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(s);
vis[s]=1;
dep[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(!vis[v]&&cap[i]>flo[i])
{
vis[v]=1;
dep[v]=dep[u]+1;
q.push(v);
}
}
}
//cout<<vis[t]<<endl;
return vis[t];
}
long long dfs(int s,int t,int u,long long a)
{
if(u==t||a==0)
{
return a;
}
long long flow=0,f;
cur[u]=head[u];
for(int i=cur[u];i;i=nxt[i])
{
int v=to[i];
cur[u]=i;
if(dep[u]+1==dep[v]&&(f=dfs(s,t,v,min(a,cap[i]-flo[i])))>0)
{
flo[i]+=f;
flo[i^1]-=f;
flow+=f;
a-=f;
if(a==0)
{
break;
}
}
}
return flow;
}
long long maxFlow(int s,int t)
{
long long flow=0;
while(bfs(s,t))
{
memset(cur,0,sizeof(cur));
flow+=dfs(s,t,s,INF);
}
return flow;
}
int main()
{
//freopen("in.txt","r",stdin);
cin>>n>>m>>s>>t;
cnt=1;
for(int i=0;i<m;i++)
{
cin>>u>>v>>c;
addEdge(u,v,c);
addEdge(v,u,0);
}
cout<<maxFlow(s,t);
}
by Xqbk @ 2021-07-25 11:37:36
邻接表可以过换前向星就不行qwq
by 绝顶我为峰 @ 2021-07-25 11:45:43
前向星常数大,有问题吗