NOI 2008第一试

兔子

题目名称                假面舞会          设计路线            志愿者招募
目录                         party                 design             employee
可执行文件名           party                 design             employee
输入文件名             party.in            design.in           employee.in
输出文件名             party.out        design.out          employee.out
每个测试点时限         1s                     2s                         2s
内存限制                 128M               128M                      128M
测试点数目               10                     10                           10
每个测试点分值        10                     10                           10
是否有部分分           无                       有                           无
题目类型                传统                   传统                        传统

提交源程序须加后缀
对于Pascal 语言   party.pas      design.pas     employee.pas
对于C 语言           party.c          design.c         employee.c
对于C++ 语言       party.cpp      design.cpp     employee.cpp
注意：最终测试时，所有编译命令均不打开任何优化开关
题1

---

假面舞会
【问题描述】
一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己喜欢的面具。每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。
为了使舞会更有神秘感，主办方把面具分为k (k≥3)类，并使用特殊的技术将每个面具的编号标在了面具上，只有戴第i 类面具的人才能看到戴第i+1 类面具的人的编号，戴第k 类面具的人能看到戴第1 类面具的人的编号。
参加舞会的人并不知道有多少类面具，但是栋栋对此却特别好奇，他想自己算出有多少类面具，于是他开始在人群中收集信息。
栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第2号面具的人看到了第5 号面具的编号。栋栋自己也会看到一些编号，他也会根据自己的面具编号把信息补充进去。
由于并不是每个人都能记住自己所看到的全部编号，因此，栋栋收集的信息不能保证其完整性。现在请你计算，按照栋栋目前得到的信息，至多和至少有多少类面具。由于主办方已经声明了k≥3，所以你必须将这条信息也考虑进去。

【输入格式】
输入文件 party.in 第一行包含两个整数n, m，用一个空格分隔，n 表示主办方总共准备了多少个面具，m 表示栋栋收集了多少条信息。
接下来m 行，每行为两个用空格分开的整数a, b，表示戴第a 号面具的人看到了第b 号面具的编号。相同的数对a, b 在输入文件中可能出现多次。

【输出格式】
输出文件 party.out 包含两个数，第一个数为最大可能的面具类数，第二个数为最小可能的面具类数。如果无法将所有的面具分为至少3 类，使得这些信息都满足，则认为栋栋收集的信息有错误，输出两个-1。

【输入样例一】
6 5
1 2
2 3
3 4
4 1
3 5
【输出样例一】
4 4

【输入样例二】
3 3
1 2
2 1
2 3
【输出样例二】
-1 -1

【数据规模和约定】
50%的数据，满足n ≤ 300, m ≤ 1000；
100%的数据，满足n ≤ 100000, m ≤ 1000000。

题2

---

设计路线
【问题描述】
Z 国坐落于遥远而又神奇的东方半岛上，在小Z 的统治时代公路成为这里主要的交通手段。Z 国共有n 座城市，一些城市之间由双向的公路所连接。非常神奇的是Z 国的每个城市所处的经度都不相同，并且最多只和一个位于它东边的城市直接通过公路相连。Z 国的首都是Z 国政治经济文化旅游的中心，每天都有成千上万的人从Z 国的其他城市涌向首都。
为了使Z 国的交通更加便利顺畅，小Z 决定在Z 国的公路系统中确定若干条规划路线，将其中的公路全部改建为铁路。
我们定义每条规划路线为一个长度大于1 的城市序列，每个城市在该序列中最多出现一次，序列中相邻的城市之间由公路直接相连(待改建为铁路)。并且，每个城市最多只能出现在一条规划路线中，也就是说，任意两条规划路线不能有
公共部分。
当然在一般情况下是不可能将所有的公路修建为铁路的，因此从有些城市出发去往首都依然需要通过乘坐长途汽车，而长途汽车只往返于公路连接的相邻的城市之间，因此从某个城市出发可能需要不断地换乘长途汽车和火车才能到达首
都。
我们定义一个城市的“不便利值”为从它出发到首都需要乘坐的长途汽车的次数，而Z 国的交通系统的“不便利值”为所有城市的不便利值的最大值，很明显首都的“不便利值”为0。小Z 想知道如何确定规划路线修建铁路使得Z 国的
交通系统的“不便利值”最小，以及有多少种不同的规划路线的选择方案使得“不便利值”达到最小。当然方案总数可能非常大，小Z 只关心这个天文数字mod Q后的值。
注意：规划路线1-2-3 和规划路线3-2-1 是等价的，即将一条规划路线翻转依然认为是等价的。两个方案不同当且仅当其中一个方案中存在一条规划路线不属于另一个方案。

【输入格式】
输入文件 design.in 第一行包含三个正整数N、M、Q，其中N 表示城市个数，M 表示公路总数，N 个城市从1~N 编号，其中编号为1 的是首都。Q 表示上文提到的设计路线的方法总数的模数。接下来M 行，每行两个不同的正数ai、bi (1≤
ai , bi ≤ N)表示有一条公路连接城市ai 和城市bi。 输入数据保证一条公路只出现一次。

【输出格式】
输出文件 design.out 应包含两行。第一行为一个整数，表示最小的“不便利值”。 第二行为一个整数，表示使“不便利值”达到最小时不同的设计路线的方法总数 mod Q 的值。
如果某个城市无法到达首都，则输出两行-1。

【输入样例】
5 4 100
1 2
4 5
1 3
4 1

【输出样例】
1
10

【样例说明】
以下样例中是 10 种设计路线的方法：
(1) 4-5
(2) 1-4-5
(3) 4-5, 1-2
(4) 4-5, 1-3
(5) 4-5, 2-1-3
(6) 2-1-4-5
(7) 3-1-4-5
(8) 1-4
(9) 2-1-4
(10) 3-1-4

【数据规模和约定】
对于 20%的数据，满足N,M ≤ 10。
对于50%的数据，满足N,M ≤ 200。
对于60%的数据，满足N,M ≤ 5000。
对于100%的数据，满足1 ≤ N,M ≤ 100000，1 ≤ Q ≤ 120000000。

【评分方式】
每个测试点单独评分。对于每个测试点，第一行错则该测试点得零分，否则若第二行错则该测试点得到40%的分数。如果两问都答对，该测试点得到100%的分数。

题3

---

志愿者招募
【问题描述】
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。
布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是
布布找到了你，希望你帮他设计一种最优的招募方案。

【输入格式】
输入文件employee.in 的第一行包含两个整数N, M，表示完成项目的天数和
可以招募的志愿者的种类。
接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。
接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起
见，我们可以认为每类志愿者的数量都是无限多的。

【输出格式】
输入文件 employee.out 中仅包含一个整数，表示你所设计的最优方案的总费
用。

【输入样例】
3 3
2 3 4
1 2 2
2 3 5
3 3 2

【输出样例】
14

【样例说明】
招募 3 名第一类志愿者和4 名第三类志愿者。

【数据规模和约定】
30%的数据中，1 ≤ N, M ≤ 10，1 ≤ Ai ≤ 10；
100%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均
不超过2[sup]31[/sup]-1。