dinic板子的又一个问题
  • 板块灌水区
  • 楼主caibet
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/8/14 15:06
  • 上次更新2023/11/3 03:53:42
查看原帖
dinic板子的又一个问题
392304
caibet楼主2023/8/14 15:06

标准的当前弧优化是这样的:

		for(int &i=cur[x];i;i=nxt[i]){
			if(!v[i]||dis[to[i]]!=dis[x]+1) continue;
			ll num=dfs(to[i],min(w,v[i]));
			res+=num;
			w-=num;
			v[i]-=num;
			v[i^1]+=num;
			if(!w) break;
		}

以下这种当前弧优化会 TLE:

		for(int i=cur[x];i;i=cur[x]){// 这一行不同
			cur[x]=nxt[cur[x]];// 这一行不同
			if(!v[i]||dis[to[i]]!=dis[x]+1) continue;
			ll num=dfs(to[i],min(w,v[i]));
			res+=num;
			w-=num;
			v[i]-=num;
			v[i^1]+=num;
			if(!w) break;
		}

按照我的理解,每次遍历到点 x 时,cur[x] 就会指向点 x 下一步需要走的边而不会发生重复。而事实上它跑的非常慢。

(这是为什么

2023/8/14 15:06
加载中...