交了两次,两次之间只有如下dfs当前弧优化的一处,其余部分均相同,而加上当前弧优化后会T,不加反而跑的很快。经本地测试,两份代码输出相同,然而加上当前弧优化的那一份代码进行增广的次数远远大于不加当前弧优化的代码(前者7000次左右,后者30次左右)且每次的流量很少(少量多次),导致的超时。我的当前弧优化没写假,而且之前写的很多题从来没遇到过加上当前弧优化后跑的更慢的情况。求解答为什么这道题的情况截然相反。
加了当前弧优化的代码,TLE 25pts
struct _eg{int pre,v,c;}eg[maxm*2];int ei=1,eh[maxn],cur[maxn];
inline void ea(int u,int v,int c){eg[++ei]={eh[u],v,c};eh[u]=ei;}
int dfs(int u,int fl,int t){
if(u==t)return fl;int sum=0;
for(int e=cur[u];e&&fl;cur[u]=e=eg[e].pre){
auto &[_,v,c]=eg[e];
if(c>0&&dis[u]+1==dis[v]){
int can=dfs(v,min(c,fl),t);
if(can==0){dis[v]=inf;continue;}
eg[e].c-=can,eg[e^1].c+=can;
fl-=can,sum+=can;
}
}
return sum;
}