首页 > 代码库 > 省队集训 Day3 吴清华
省队集训 Day3 吴清华
【题目大意】
给网格图,共有$n * n$个关键节点,横向、纵向距离均为$d$,那么网格总长度和宽度均为$(n+1) * d + 1$,最外围一圈除了四角是终止节点。要求每个关键节点都要通过线连向终止节点,每个点只能连一条线,线不能相交,且只能连在网格的边上。
求最短布线距离。提交答案题。
【题解】
前面3个点(60分)可以跑费用流,这是一个经典拆点费用流模型,大概并行跑个15min也就出来了。
后面2个点据说用原始对偶跑会快很多,ditoly后两个点就跑了36分。
orz ditoly
省队集训 Day3 吴清华
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。