编程介的小学生 2017-03-01 14:39 采纳率: 20.5%
浏览 774
已采纳

All Discs Considered

Operating systems are large software artefacts composed of many packages, usually distributed on several media, e.g., discs. You probably remember the time when your favourite operating system was delivered on 21 floppy discs, or, a few years later, on 6 CDs. Nowadays, it will be shipped on several DVDs, each containing tens of thousands of packages.

The installation of certain packages may require that other packages have been installed previously. Therefore, if the packages are distributed on the media in an unsuitable way, the installation of the complete system requires you to perform many media changes, provided that there is only one reading device available, e.g., one DVD-ROM drive. Since you have to start the installation somehow, there will of course be one or more packages that can be installed independently of all other packages.

Given a distribution of packages on media and a list of dependences between packages, you have to calculate the minimal number of media changes required to install all packages. For your convenience, you may assume that the operating system comes on exactly 2 DVDs.

Input Specification

The input contains several test cases. Every test case starts with three integers N1, N2, D. You may assume that 1<=N1,N2<=50000 and 0<=D<=100000. The first DVD contains N1 packages, identified by the numbers 1, 2, ..., N1. The second DVD contains N2 packages, identified by the numbers N1+1, N1+2, ..., N1+N2. Then follow D dependence specifications, each consisting of two integers xi, yi. You may assume that 1<=xi,yi<=N1+N2 for 1<=i<=D. The dependence specification means that the installation of package xi requires the previous installation of package yi. You may assume that there are no circular dependences. The last test case is followed by three zeros.

Output Specification

For each test case output on a line the minimal number of DVD changes required to install all packages. By convention, the DVD drive is empty before the installation and the initial insertion of a disc counts as one change. Likewise, the final removal of a disc counts as one change, leaving the DVD drive empty after the installation.

Sample Input

3 2 1
1 2
2 2 2
1 3
4 2
2 1 1
1 3
0 0 0
Sample Output

3
4
3

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-03-07 15:09
    关注

    http://www.cnblogs.com/lahblogs/p/3560922.html

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题？

  • All Discs Considered
    2017-03-01 14:39
    回答 2 已采纳 http://www.cnblogs.com/lahblogs/p/3560922.html
  • Jack and Jill's Compact Discs
    2016-11-13 04:56
    回答 1 已采纳 http://blog.csdn.net/u010372095/article/details/9004723
  • Othello
    2017-05-05 06:10
    回答 1 已采纳 https://www.baidu.com/link?url=l6At766DL7pNTpTAgpaf3Iuqvr3BIdTdlRQMRDmt4aXhexKazsuMXiPUWxOHKOkjGfFSd
  • 算法设计 第二次上机 All discs considered
    2017-11-07 15:48
    lxlybytwo的博客 总时间限制: 10000ms 内存限制:...描述Operating systems are large software artefacts composed of many packages, usually distributed on several media, e.g., discs. You probably remember the time when you
  • Viva Confetti less
    2017-10-17 00:14
    回答 1 已采纳 http://blog.csdn.net/u010579068/article/details/45201121
  • 使用DOMXPath在PHP中调用XML数据 php xml
    2018-10-01 03:03
    回答 1 已采纳 The problem is that there is a namespace on your VehicleDescription element. You need to register
  • SPOJ ALL All Discs Considered 搜索
    2017-04-08 21:06
    霜刃未曾试的博客 题目：http://www.spoj.com/problems/ALL/en/题意：有两张安装盘，每张盘上都有一些安装包，某些安装包依赖于另外一些安装包，也就安装一个安装包时，要求已经安装了特定的包，读入设备每次只能读一个盘，问要安装完...
  • POJ_All Discs Considered
    2017-10-20 16:30
    lxt_bupt的博客 总时间限制: 10000ms 内存限制:...描述Operating systems are large software artefacts composed of many packages, usually distributed on several media, e.g., discs. You probably remember the time when you
  • poj1778 All Discs Considered
    2017-10-22 14:50
    weixin_30438813的博客 思路： 拓扑排序。贪心。 实现： 1 #include <bits/stdc++.h> 2 using namespace std; 3 vector<int> G[100005]; 4 int n1, n2; 5 inline void help(queue<... b,...
  • POJ 1778 All Discs Considered（拓扑排序）
    2014-02-22 18:29
    1361976860的博客 点我看题目 题意 ：其实题意我也说不清楚，因为比赛的时候我盯着看了1个小时也没看懂。。。。就是两个磁盘，第一个有n1的安装包，编号为1~n1，第二个有n2个安装包，编号为n1~n2。给你d对关系，（x，y）代表着安装x...
  • All Discs Considered(拓扑排序)
    2014-02-22 15:55
    詹小布的博客 题意：有两个DVD，第一个DVD上有编号为1~n1的安装包，第二个DVD上有编号为n1+1~n1+n2的安装包，给出m组关系(a,b) 表示安装a之前必须先安装b。由于安装时每次只能插入一个DVD，问安装完所有的安装包，这两个DVD至少...
  • POJ 1778 All Discs Considered G++ 拓扑排序 巧妙 图的数据结构 没掌握
    2017-06-04 21:30
    woniupengpeng的博客 2张盘安装软件。第一张盘有N1个软件，1到N1命名。第二张盘有N2个软件，N1+1到N1+N2命名。软件之间有D个依赖关系。xi 必须先于 yi安装。求光盘拔插次数。
  • HDU 题目分类（转载）
    2020-02-15 01:11
    shiftrain的博客 基础题：1000、1001、1004、1005、1008、1012、1013、1014、1017、1019、1021、1028、1029、 1032、1037、1040、1048、1056、1058、1061、1070、1076、1089、1090、1091、1092、1093、 1094、1095、1096、1097、...
  • POJ刷题顺序
    2020-03-03 23:02
    Ordinary_yfz的博客 Catch them 0.3 9986 32321 1276 Cash Machine 0.35 9980 27960 3461 ...All Out 0.34 9792 28332 2109 Power of Cryptography 0.5 9749 19316 1080 Human Gene Functions 0.55 9605 17277 2140 Herd Sums 0.59 9503...
  • POJ题目难易总汇
    2020-03-06 15:47
    Modestr-E·X·L的博客 1936 All in All 0.41 11783 28512 1067 取石子游戏 0.33 11731 34989 3259 Wormholes 0.36 11604 31956 1321 棋盘问题 0.49 11535 23260 1611 The Suspects 0.48 11323 23303 1552 Doubles 0.57 11238 19409 ...
  • HDOJ题目分类
    2019-09-27 02:33
    ao350322的博客 1147 All Discs Considered 搜索：BFS 1148 In Danger 模拟题 1149 Run Length Encoding 字符串处理 1150 Bee Maja 模拟题 1151 Friends 表达式求值 1152 John 博弈论 1153 Double Queue 最大堆与最小堆 1154...
  • HDU分类
    2019-08-11 22:07
    xu-bu-ji的博客 1032、1037、1040、1048、1056、1058、1061、1070、1076、1089、1090、1091、1092、1093、 1094、1095、1096、1097、1098、1106、1108、1157、1163、1164、1170、1194、1196、1197、 1201、1202、1205、1219、1234...
  • HDU题目分类大全【大集合】
    2019-03-18 20:48
    扣子不会飞的博客 基础题： 1000、1001、1004、1005、1008、1012、1013、1014、1017、1019、1021、1028、1029、 1032、1037、1040、1048、1056、1058、1061、1070、1076、1089、1090、1091、1092、1093、 1094、1095、1096、1097、...
  • HDOJ 题目类型
    2019-05-02 23:24
    weixin_30521649的博客 1147 All Discs Considered 搜索：BFS 1148 In Danger 模拟题 1149 Run Length Encoding 字符串处理 1150 Bee Maja 模拟题 1151 Friends 表达式求值 1152 John 博弈论 1153 Double Queue 最大堆与最小堆 1154 ‘JBC...
  • 杭电题目分类
    2019-05-01 16:10
    &七里香&的博客 **hdu题目大致分类：（详细分类在后） 模拟题, 枚举 1002 1004 1013 1015 1017 1020 1022 1029 1031 1033 1034 ...1147 All Discs Considered 搜索：BFS 1148 In Danger 模拟题 1149 Run Length Encoding 字符串...
  • 没有解决我的问题, 去提问

悬赏问题

  • ¥15 uniapp uview http 如何实现统一的请求异常信息提示？
  • ¥15 有了解d3和topogram.js库的吗？有偿请教
  • ¥100 任意维数的K均值聚类
  • ¥15 stamps做sbas-insar，时序沉降图怎么画
  • ¥15 买了个传感器，根据商家发的代码和步骤使用但是代码报错了不会改，有没有人可以看看
  • ¥15 关于#Java#的问题，如何解决？
  • ¥15 加热介质是液体，换热器壳侧导热系数和总的导热系数怎么算
  • ¥100 嵌入式系统基于PIC16F882和热敏电阻的数字温度计
  • ¥15 cmd cl 0x000007b
  • ¥20 BAPI_PR_CHANGE how to add account assignment information for service line