求调费用流模板题

P4015 运输问题

你的建图没有错,建议好好查查费用流板子,当然也可能是清空的问题
by Iniaugoty @ 2023-12-09 23:47:21


@[gty314159](/user/768612) 我觉得多半就是板子的问题,毕竟我是拿这个当板子题做得的,所以板子不是粘贴的。谢谢您!
by Kniqht @ 2023-12-10 08:23:49


妈得,最抽象的一集: ```cpp void build(int T){ s=0,t=n+m+1; for(int i=1;i<=m;i++) add(s,i,a[i],0),add(i,s,0,0); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) add(i,j+m,b[j],cost[i][j]*t),add(j+m,i,0,-cost[i][j]*t); for(int i=1;i<=n;i++) add(i+m,t,b[i],0),add(t,i+m,0,0); } ``` 可以发现一个奇怪的地方,我让费用乘上了终点坐标!其实应该是传参的大写T才对,破防了。 还有就是第二个输出maxflow应该取反(虽然maxflow这个变量名不是很准确,,,应该是mincost和maxcost)
by Kniqht @ 2023-12-10 10:10:39


|