首页 > 代码库 > ●BZOJ 4289 PA2012 Tax
●BZOJ 4289 PA2012 Tax
●赘述题目
算了,题目没有重复的必要。
注意理解:对答案造成贡献的是每个点,就是了。
举个栗子:
对于如下数据:
2 1
1 2 1
答案是 2;
●题解
方法:建图(难点)+最短路。
先来几个链接:(他们为我解题提供了思路,但有些部分看得我有点mengbi)
●http://blog.csdn.net/pure_w/article/details/55060079
●http://www.cnblogs.com/clrs97/p/5046933.html
建图:
1.把原图的双向边拆成两条单向边(权值不变)。并把每条单向边看成一个点(称为新图点);
2.建立源点S,S向1号点的出边(新图点)建单向边,权值为那些出边的权值。
3.建立汇点T,n号点的入边(新图点)向T建单向边,权值为那些入边的权值。
效果如下:
接下来是比较暴力的建边
(4.)枚举每个原图点,把它的每条入边(新图点)向每条出边(新图点)建边,权值为这两条出入边的较大权值。(这样导致边巨多)
4.(似乎叫差分边),枚举每个原图点,先把它的出边(新图点)从小到大排序,排序后相邻的出边(新图点)间建两条有向边,小的指向大的边权为两者权值之差,大的指向小的边权为0。再枚举它的每个入边(新图点),向该原图点的与它权值相同的出边建边(),权值就为该相同权值。
●BZOJ 4289 PA2012 Tax
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。