萌新求助差分约束
查看原帖
萌新求助差分约束
414386
Isshiki·Iroha楼主2021/9/25 10:35

对于本题:

建边是这样的:

for(ri i(1),u,v,w; i<=m; ++i) {
	read(u,v,w);
	add(v,u-1,-w);
	add(u-1,v,w);
}
for(ri i(1); i<=n; ++i) {
	add(n+1,i,0);
}

但是对于P1250

for(ri i(1),u,v,w; i<=m; ++i) {
	read(u,v,w);
	add(u-1,v,w);
}
for(ri i(0); i<n; ++i) {
	add(i,i+1,0);
	add(i+1,i,-1);
}

这两个题的建边很像,一个是正反都约束了一次,还有一个是只正着约束。

是因为第一题没有其他约束条件了,就正反都约束吗?

或者因为第二题有其他约束条件了,就不需要这个限制了吗?(第二题我加了之后 TLE 了)。

求助为什么?我不太明白

2021/9/25 10:35
加载中...