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 cmonkey at 2012-02-14 20:26:33 on Problem 1636
开始看样例的时候注意到了,但是写的时候却忽略了,尤其在邻接表建边的时候,读进来直接就往里加边...
因为这个WA了一次,感觉没有坑,过了样例就行

简述下算法
预处理,将人分成互相有影响的几个集合,集合内的人要走就必须全部走。把集合看做一个属性为(p,q)的物品(表示prison1中有p人,prison2中有q人)放到背包(m/2,m/2)中
当然,无影响的人就是(1,0)或(0,1)
然后,普通的可行性背包

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