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 jinyingqi at 2011-04-11 16:42:47 on Problem 1087
http://blog.csdn.net/koala002/archive/2011/04/11/6315924.aspx
题意:现在有m个设备,n种电源插座,k个适配器。适配器a b作用为可以把a插头转成b插头,也就是原来用a电源的设备现在可以用b电源

需要注意的几点:

1、"only one receptacle of each type",对于n种电源插座,每种类型只有一个

2、"No two devices will have exactly the same name",对于m个设备,彼此不相同

3、1<=m,n,k<=100,所以最多出现电源类型数为4*100=400,再加个m个设备与一个源点一个汇点,邻接矩阵的大小最少应为502.

4、适配器的数量是无限的

5、求最小几个设置没有电源

分析:一道很标准的网络最大流问题,关键在于建图

1、取源点、汇点分别标号0,1

2、源点到n个电源有容量为1的边

3、相应电源到m个设备有一条容量为1的边

4、m个设备到汇点有一条容量为1的边

5、k个适配器,如果a b,表示b电源可以转换成a电源,即电源b到电源a有一条容量无限的边

6、求源点到汇点网络最大流量


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