蒟蒻问一个关于 Dinic 的问题
  • 板块学术版
  • 楼主isitover
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/11/4 14:41
  • 上次更新2023/11/4 01:28:01
查看原帖
蒟蒻问一个关于 Dinic 的问题
558743
isitover楼主2021/11/4 14:41

两种写法有什么区别?请问还有很好的写法或者哪里可以优化吗?

inline int dinic(int u,int sum){
    if(u==t) return sum;
    int ret=0;
    for(int i=now[u];i;i=nxt[i]){
	now[u]=i;
	int v=ver[i];
	if(val[i]&&d[v]==d[u]+1){
	    int k=dinic(v,min(sum-ret,val[i]));
	    val[i]-=k;val[i^1]+=k;
	    ret+=k;
	    if(ret==sum) return sum;
	}
    }
    return ret;
}
inline int dinic(int u,int sum){
    if(u==t) return sum;
    int k,res=0;
    for(int i=now[u];i&∑i=nxt[i]){
	now[u]=i;
	int v=ver[i];
	if(val[i]&&d[v]==d[u]+1){
	    k=dinic(v,min(sum,val[i]));
	    if(k==0) d[v]=inf;
	    val[i]-=k;
	    val[i^1]+=k;
	    res+=k;
	    sum-=k;
	}
    }
    return res;
}
2021/11/4 14:41
加载中...