《《alice′schance》解题报告》由会员分享，可在线阅读，更多相关《《alice′schance》解题报告（5页珍藏版）》请在金锄头文库上搜索。
1、Alices Chance解题报告解题报告题目来源：http:/ （No.1698） 解法或类型：网络流 作者：谢迪题目描述题目描述Alices ChanceTime Limit:1S Memory Limit:2000K Total Submit:98 Accepted:44Description Alice, a charming girl, have been dreaming of being a movie star for long. Her chances will come now, for several filmmaking companies invite her to
2、play the chief role in their new films. Unfortunately, all these companies will start making the films at the same time, and the greedy Alice doesnt want to miss any of them! You are asked to tell her whether she can act in all the films. As for a film, 1. it will be made ONLY on some fixed days in
3、a week, i.e., Alice can only work for the film on these days; 2. Alice should work for it at least for specified number of days; 3. the film MUST be finished before a prearranged deadline.For example, assuming a film can be made only on Monday, Wednesday and Saturday; Alice should work for the film
4、at least for 4 days; and it must be finished within 3 weeks. In this case she can work for the film on Monday of the first week, on Monday and Saturday of the second week, and on Monday of the third week. Notice that on a single day Alice can work on at most ONE film. Input The first line of the inp
5、ut contains a single integer T (1 = T = 20), the number of test cases. Then T cases follow. Each test case begins with a single line containing an integer N (1 = N = 20), the number of films. Each of the following n lines is in the form of “F1 F2 F3 F4 F5 F6 F7 D W“. Fi (1 = i = 7) is 1 or 0, repres
6、enting whether the film can be made on the i-th day in a week (a week starts on Sunday): 1 means that the film can be made on this day, while 0 means the opposite. Both D (1 = D = 50) and W (1 = W = 50) are integers, and Alice should go to the film for D days and the film must be finished in W weeks
7、.Output For each test case print a single line, Yes if Alice can attend all the films, otherwise No.Sample Input 2 2 0 1 0 1 0 1 0 9 3 0 1 1 1 0 0 0 6 4 2 0 1 0 1 0 1 0 9 4 0 1 1 1 0 0 0 6 2Sample Output Yes NoHint A proper schedule for the first test case:date Sun Mon Tue Wed Thu Fri Sat week1 film
8、1 film2 film1 film1 week2 film1 film2 film1 film1 week3 film1 film2 film1 film1 week4 film2 film2 film2Source Alcyone解题思路解题思路本题可以通过建立适当的图论模型来解决。 可以这样构图：把每一部电影作为一个结点 ai，把每一天时间也作为一个结点 bj，其 中总的天数为 maxW * 7，其中 W 表示每部电影必须在 W 星期内完成。并设置一个源点 s 和汇点 t。 这样，若第 i 部电影需要在 Wi 星期内完成，它的拍摄只能在每周的 d1, d2, d3, , dm 进行，那么
9、就从 ai 向 bdj + k * 7(1=j=m, 0 = k Wi)连一条容量为 1 的弧。 如：若输入的某部电影为： 0 1 0 0 1 0 1 4 2 构图如下：其中的弧容量都是 1Day1 Day2 Day3 Day4 Week 1 Day5 Day6 Day7 Day8 Day9 Day10 Day11 Week 2 Day12 Day13 Day14 Film i然后从源点向 ai 连一条容量为 Di(Alice should go to the film i for Di days)的弧。从 bj 向 汇点连一条容量为 1 的弧，因为：On a single day Alice
10、 can work on at most ONE film。 比如：某组数据如下： 2 0 1 0 0 1 0 1 4 2 0 1 0 0 0 1 0 2 1 则完整的构图如下： 其中标的数字表示弧的容量，未标数字的弧容量均为 1。Day1 Day2 Day3 Day4 Week 1 Day5 Day6 Day7 Day8 Day9 Day10 Day11 Week 2 Day12 Day13 Day14Film 1Film 2TS42最后，我们只要求该网络的最大流，若总流量等于每部电影需要拍摄的天数之和，则 输出“Yes” ， 否则输出“No” 。 容易看到，这样构图是满足题目要求的：1it
11、 will be made ONLY on some fixed days in a week, i.e., Alice can only work for the film on these days; 2Alice should work for it at least for specified number of days; 3the film MUST be finished before a prearranged deadline.另外本题也可以采用二分图的最大匹配来做。数据结构数据结构本题我采用的是邻接表+邻接矩阵做的。 虽然这样做比较费空间，但是在空间允许的范围内，这样既可以像邻接表一样速度比 较快，又可以像邻接矩阵一样操作方便。 char c380380, f380380; 用邻接矩阵记录网络的容量和流量 short q400, fa400; 增广时所用的队列和记录增广路径的数组 bool v400; 记录增广路径是否为后向弧时空分析：时空分析：时间复杂度为：O(mt)，其中 m 为网络中弧的个数，m 20 * 350 + 20 + 350，t 为增广 的次数(t = 1000)。 空间复杂度为：O(n2)，n 380。源程序：源程序：1698_XieDi.cpp
