 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| 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 | |||||||||
Re:以前不懂，现在似乎懂了In Reply To:Re:题都没看懂，就套个匈牙利就过了…………………… Posted by:200941841234 at 2011-08-20 16:14:19 主要是构图：将每一行当成一个点，构成集合1， 每一列也当成一个点，构成集合2；每一个障碍物的位置坐标将集合1与集合2中的点连接起来，也就是将每一个障碍物作为连接节点的边。这样可以轻易的得出本题是一个最小点覆盖的问题，假设1个行节点覆盖了5个列节点，即这个行节点与这5个列节点间有5条边（即五个障碍物），由于这5条边都被那个行节点覆盖，即表明这5个障碍物都在同一列上，于是可以一颗炸弹全部清除，而本题也就转化成求最小点覆盖数的问题。 又有一个定理是：最小点覆盖数 = 最大匹配数， 所以此题转化成求最大匹配数。 Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
