luogu P 3376【テンプレート】ネットワーク最大ストリームテンプレート
5994 ワード
#include
#include
#include
#define N 200005
using namespace std;
#define int long long
int n,m,S,T,tmp1,tmp2,tot;
int idx,head[N],cur[N],q[N],ans1[N],ans2[N];
int e[N],ne[N],w[N];
bool b[N];
int r[N],c[N];
inline void add(int u,int v,int f)
{
e[idx]=v;
w[idx]=f;
ne[idx]=head[u];
head[u]=idx++;
}
inline bool bfs()
{
int f=0,t=0;
memset(cur,-1,sizeof(cur));
q[t++]=S;
cur[S]=0;
while(f<t)
{
int now=q[f++];
for(int i=head[now]; ~i; i=ne[i])
{
int v=e[i];
if(cur[v]==-1&&w[i])
{
cur[v]=cur[now]+1;
q[t++]=v;
}
}
}
if(cur[T]!=-1)
return 1;
return 0;
}
inline int dfs(int x,int f)
{
if(x==T)
return f;
int w1,used=0;
for(int i=head[x]; ~i; i=ne[i])
{
int v=e[i];
if(cur[v]==cur[x]+1&&w[i])
{
w1=dfs(v,min(f-used,w[i]));
w[i]-=w1;
w[i^1]+=w1;
used+=w1;
if(used==f)
return f;
}
}
if(!used)
cur[x]=-1;
return used;
}
void dinic()
{
while(bfs())
tot+=dfs(S,0x3f3f3f3f);
}
signed main()
{
memset(head,-1,sizeof head);
cin>>n>>m>>S>>T;
for(int i=1; i<=m; i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,0);
}
dinic();
cout<endl;
return 0;
}