Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
并查集做法//问题描述有n个城市每个城市有g[i]黄金,b[i]的仓库容量,城市之间有道路,现在要使得所有的黄金都运入仓库 //在这个过程中所经过的最大的边权值最小,乍一看感觉是个网络流,不过那个最大最小边权给了一个启示,排序 //从小到大进行处理,如果出现了可行解吧当前边长输出即可,那么如何处理呢 //最后处理过后一定不会有回路,否则必定可以使之去掉些边,达到相同的效果,那么最后必定成了一颗树,也就是说在药生成回路时可以忽略些操作 //允许中间过程中仓库的负载,即假设当前城市有x黄金,把他劝放入到容量为y的仓库,若y<x,此时容量为y-x //问题的重点可以放到容量的变化上了,然后记录下有多少个城市需要输出黄金,最终只要看这个个数是否会为0,否则无解 //如果两个仓库都是负载,把压力给一个仓库,而这个城市就是该连通图的代表元素集,问题全部集中在他的仓库上 //这里就借助一个并查集来实现对边所带的顶点的合并,同时更新流量,以及待调整的城市数 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator