警示后人
查看原帖
警示后人
420129
Nt_Tsumiki楼主2022/10/16 17:04

如果你习惯压行的话,你的当前弧可能这么写:

for (int &i=cur[x];i and flow;i=e[i].nxt) {
    int y=e[i].to;
    if (e[i].dis and vis[y]==vis[x]+1) {
        int k=dfs(y,std::min(e[i].dis,flow));
        if (!k) {
          	vis[y]=-1;
           	continue;
        }
    	e[i].dis-=k,e[i^1].dis+=k,res+=k,flow-=k;
    }
}

但这样会 T 掉(被卡了半个小时),所以推荐这么写:

for (int i=cur[x];i and flow;i=e[i].nxt) {
    int y=e[i].to; cur[x]=i;
    if (e[i].dis and vis[y]==vis[x]+1) {
        int k=dfs(y,std::min(e[i].dis,flow));
        if (!k) {
          	vis[y]=-1;
           	continue;
        }
    	e[i].dis-=k,e[i^1].dis+=k,res+=k,flow-=k;
    }
}

至于原因,根据大佬解释,是因为赋值操作会被优化进寄存器中,所以要快(大概是

2022/10/16 17:04
加载中...