无尽星空 @ 2020-08-10 16:15:53
#include<bits/stdc++.h>
#define LL long long
#define R register int
using namespace std;
const int N=205,M=10005;
int n,m,h[N],to[M],nx[M],cnt=1,now[N],d[N],s,t;
LL flow[M],ans,inf=10000000000;
queue<int> q;
void add(int x,int y,int fl) {to[++cnt]=y;flow[cnt]=fl;nx[cnt]=h[x];h[x]=cnt;}
inline int read()
{
int s=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) s=(s<<3)+(s<<1)+(c^48),c=getchar();
return s;
}
bool bfs()
{
int x;
for(x=1;x<=n;x++) d[x]=0,now[x]=h[x];
while(q.size()) q.pop();
q.push(s);d[s]=1;
while(q.size())
{
x=q.front();q.pop();
for(R i=h[x];i>1;i=nx[i])
{
int y=to[i];
if(flow[i]&&!d[y])
{
q.push(y);
d[y]=d[x]+1;
if(y==t) return 1;
}
}
}
return 0;
}
inline LL dinic(int x,LL fl)
{
if(x==t) return fl;
LL lft=fl,us;
int i=now[x];
for(;i>1&&lft;i=nx[i])
{
int y=to[i];
if(flow[i]&&d[y]==d[x]+1)
{
us=dinic(y,min(lft,flow[i]));
if(!us) d[y]=0;
flow[i]-=us;
flow[i^1]+=us;
lft-=us;
}
}
now[x]=i;
return fl-lft;
}
int main()
{
n=read();m=read();s=read(),t=read();
while(m--)
{
int x=read(),y=read(),z=read();
add(x,y,z);add(y,x,0);
}
LL fl=0;
while(bfs())
while(fl=dinic(s,inf)) ans+=fl;
printf("%lld",ans);
return 0;
}
附:评测记录
ps:按照题目说法,#10 也不对劲
by 无尽星空 @ 2020-08-10 16:52:36
ppps:
把当前弧改了个位置:48ms
???!!!
只是由
int i=now[x];
for(;i>1&&lft;i=nx[i])
{
int y=to[i];
if(flow[i]&&d[y]==d[x]+1)
{
us=dinic(y,mn(lft,flow[i]));
if(!us) d[y]=0;
flow[i]-=us;
flow[i^1]+=us;
lft-=us;
}
}
now[x]=i;
改了now[x]的位置后:
int i=now[x];
for(;i>1&&lft;i=nx[i])
{
now[x]=i;
int y=to[i];
if(flow[i]&&d[y]==d[x]+1)
{
us=dinic(y,mn(lft,flow[i]));
if(!us) d[y]=0;
flow[i]-=us;
flow[i^1]+=us;
lft-=us;
}
}
810ms->48ms
问一下各位大佬为什么啊?
by JimmyFlower @ 2020-08-10 16:52:47
当时now放后面就以为没打当前弧(
by Querainy @ 2020-08-10 16:56:51
呃,这么写的话,如果dfs的循环中剩余流量也就是lft=0了,说明当前边很可能没有充满,而此时for循环仍会执行i=nx[i],所以这条边就被跳过了。另一种只写int &i=cut[x]的写法也有类似的问题。
纯属口胡,我是智障
by 无尽星空 @ 2020-08-10 16:58:34
@华山抡剑 您是大佬,我是蒟蒻
by JimmyFlower @ 2020-08-10 16:59:13
@无尽星空 us=dinic(y,mn(lft,flow[i]));
这里的递归可能要用到now[x]
,所以得边赋值边遍历,而不是最后再赋值。我的理解是这样。如果不是求轻喷。
by Querainy @ 2020-08-10 17:17:55
@JimmyFlower 我的意思是,虽然循环终止了,但是在循环终止前又i=nx[i]
了一次
by Querainy @ 2020-08-10 17:18:53
@JimmyFlower 递归不可能回到当前点,因为有bfs分层的限制
by JimmyFlower @ 2020-08-10 17:21:03
@华山抡剑 噢我sb了,那没事了