首页 > 代码库 > 省队集训 Day3 吴清华

省队集训 Day3 吴清华

【题目大意】

给网格图,共有$n * n$个关键节点,横向、纵向距离均为$d$,那么网格总长度和宽度均为$(n+1) * d + 1$,最外围一圈除了四角是终止节点。要求每个关键节点都要通过线连向终止节点,每个点只能连一条线,线不能相交,且只能连在网格的边上。

求最短布线距离。提交答案题

【题解】

前面3个点(60分)可以跑费用流,这是一个经典拆点费用流模型,大概并行跑个15min也就出来了。

后面2个点据说用原始对偶跑会快很多,ditoly后两个点就跑了36分。

orz ditoly

技术分享

 

省队集训 Day3 吴清华