无尽星空 @ 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 JimmyFlower @ 2020-08-10 16:17:20
@无尽星空 用当前弧优化
by JimmyFlower @ 2020-08-10 16:20:13
?多加了一个测试点我才发现
by 无尽星空 @ 2020-08-10 16:22:59
用了啊
by 无尽星空 @ 2020-08-10 16:23:24
@JimmyFlower now[x]
by JimmyFlower @ 2020-08-10 16:25:33
@JimmyFlower 噢抱歉,我打的方式不太一样没看见
by RainFestival @ 2020-08-10 16:34:36
@无尽星空
if (!lft) break;
by 无尽星空 @ 2020-08-10 16:46:04
找到原因了:
加当前弧优化:810ms
不加当前弧优化:75ms
!!!
令人谔谔。
……
ps:我是不是学了个fake的当前弧优化
pps:可是我照着蓝书上打的啊
by 无尽星空 @ 2020-08-10 16:46:25
感谢各位大佬
by WGNJF @ 2020-08-10 16:48:35
@无尽星空 ...就离谱
by JimmyFlower @ 2020-08-10 16:51:32
@无尽星空 hh才发现是now的位置放错了