Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

并查集做法

Posted by foreverlin at 2009-07-02 23:33:40 on Problem 3228
//问题描述有n个城市每个城市有g[i]黄金,b[i]的仓库容量,城市之间有道路,现在要使得所有的黄金都运入仓库
//在这个过程中所经过的最大的边权值最小,乍一看感觉是个网络流,不过那个最大最小边权给了一个启示,排序
//从小到大进行处理,如果出现了可行解吧当前边长输出即可,那么如何处理呢
//最后处理过后一定不会有回路,否则必定可以使之去掉些边,达到相同的效果,那么最后必定成了一颗树,也就是说在药生成回路时可以忽略些操作
//允许中间过程中仓库的负载,即假设当前城市有x黄金,把他劝放入到容量为y的仓库,若y<x,此时容量为y-x
//问题的重点可以放到容量的变化上了,然后记录下有多少个城市需要输出黄金,最终只要看这个个数是否会为0,否则无解 
//如果两个仓库都是负载,把压力给一个仓库,而这个城市就是该连通图的代表元素集,问题全部集中在他的仓库上 
//这里就借助一个并查集来实现对边所带的顶点的合并,同时更新流量,以及待调整的城市数

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator