Lucifero @ 2021-07-20 11:25:09
#include <bits/stdc++.h>
#define int long long
#define inf 0x7f7f7f7f
using namespace std;
class Edge
{
public:
int u,v,w,next;
}e[100001];
queue<int> r;
int elast[201],cur[201],level[201],cnt[201],n,s,t,link(1),ans;
void add(int u,int v,int w)
{
e[++link]=(Edge){u,v,w,elast[u]};
elast[u]=link;
}
void bfs(int u)
{
memset(level,inf,sizeof(level));
cnt[level[u]=0]=1;
r.push(u);
int v,i;
while(!r.empty())
{
u=r.front(),r.pop();
for(i=elast[u];i!=0;i=e[i].next)
{
v=e[i].v;
if (level[v]>=inf)
{
cnt[level[v]=level[u]+1]++;
r.push(v);
}
}
}
}
int augment(int u,int flow)
{
int v,k(0),temp,i;
if (u==t) return flow;
for(i=cur[u];i!=0;i=e[i].next)
{
cur[u]=i;
v=e[i].v;
if (e[i].w>0 && level[u]==level[v]+1)
{
temp=augment(v,min(flow-k,e[i].w));
e[i].w-=temp,e[i^1].w+=temp;
k+=temp;
if (k==flow || level[s]>t)
return k;
}
}
if (level[s]>t) return k;
cnt[level[u]]--;
if (!cnt[level[u]]) level[s]=t+1;
cnt[++level[u]]++;
cur[u]=elast[u];
return k;
}
signed main()
{
//¡¾Ä£°å¡¿ÍøÂç×î´óÁ÷
int m,u,v,w;
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
while(m--)
{
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);
add(v,u,0);
}
bfs(t);
while(level[s]<=t)
{
memcpy(cur,elast,sizeof(cur));
ans+=augment(s,inf);
}
printf("%lld",ans);
}
by 约瑟夫用脑玩 @ 2021-07-20 11:27:44
以前会 SAP 现在不会了qwq。
这边重构写 Dinic。
by reveal @ 2021-07-20 11:28:24
我对这是什么编码感到好奇
by Lucifero @ 2021-07-20 11:35:53
@约瑟夫用脑玩 本质不是一样的么,跟 ISAP
by 约瑟夫用脑玩 @ 2021-07-20 11:41:13
@Gray_White 但我只看得懂 Dinic。。。
SAP 里面挂了我看不出来的