建议增加数据强度
查看原帖
建议增加数据强度
662295
Flanksy楼主2023/6/29 22:31

模板题写过了,双倍经验 WA 了。

错误的写法:

long long dfs(int x,long long flow){
	if(x==T||!flow) return flow;
	long long ret=0ll;
	for(int &i=hc[x];i;i=e[i].nxt) if(d[e[i].to]==d[x]+1){
		long long now=dfs(e[i].to,min(flow,e[i].w));
		ret+=now,e[i].w-=now,e[i^1].w+=now;
		if(ret==flow) break;
	}
	return ret;
}

正确的写法:

long long dfs(int x,long long flow){
	if(x==T||!flow) return flow;
	long long ret=0ll;
	for(int &i=hc[x];i;i=e[i].nxt) if(d[e[i].to]==d[x]+1){
		long long now=dfs(e[i].to,min(flow,e[i].w));
		ret+=now,e[i].w-=now,e[i^1].w+=now;
		flow-=now;
		if(!flow) break;
	}
	return ret;
}

第一种写法的 dfs 中限制了流量但没有完全限制。建议把 P2740 的第 11 个测试点搬到本题作为 hack 数据。

2023/6/29 22:31
加载中...