1 /*   2  *    DFS   3  *    两种搜索策略， 详见 lrj《算法艺术与信息学竞赛》P183   4  *    以下有两种策略的实现   5  *   6  *   7  *    策略一： 基于“线路”：（详见注释）   8  *        另外可见 http://blog.sina.com.cn/s/blog_68629c770100wpit.html   9  *     10  *    策略二： 基于“车辆”：  11  *    [分析]（转自 http://acm.sdibt.edu.cn/blog/?p=66）  12  *        此题是明显的搜索题，且DFS较为合适。  13  *        由于每条线路只需要第一和第二辆车到达的时刻，就可以完全确定，  14  *    因此我们可以依次考虑12:00-12:59的车辆到达情况。  15  *        假设某一个时刻有一辆车到达本站，那么它有两种可能：  16  *            1) 它是一条新线路的第一辆车；  17  *            2) 它是已有某条线路的第二辆车。  18  *        如果是情况1)，那么我们需将它作一下标记。  19  *        如果是情况2)，那么我们就枚举该线路的第一辆车在何时刻到达，  20  *    有了此时刻，那么就可以完全确定这条线路，随后我们可以把这一条线路从记录中删除。  21  *    再根据题干中提到的那么约束条件，我们就可以写出程序了。  22  *    （代码转自 http://hi.baidu.com/lin791263068/blog/item/7c349de8f5204221279791d3.html ）（加了注释）  23  *  24  */  25  26 //策略一：  27 #include 
     
        28 #include 
      
         29 using namespace std;  30  31 struct SData{
    32     int begin;            //第一辆车到达的时刻  33     int interval;        //时间间隔  34     int times;            //车次  35 };  36 SData bus[1000];        //最多900条可能的公交车线路  37  38 int n, sum[65] = {};  39 int tot = 0, ans = 17;  40  41 bool cmp(const SData a, const SData b){
    42     return (a.times > b.times);  43 }  44  45 //以a时刻为起点，时间间隔为b的 公交车线路 是否可能存在  46 bool check(int a, int b){
    47     for(int i=a; i<60; i+=b){
    48         if(sum[i] == 0)  49             return false;  50     }  51     return true;  52 }  53 //num：当前已确定的公车路线数  54 void dfs(int t, int num){
    55     if(n <= 0){                        //搜完  56         if(num < ans) ans = num;  57         return;  58     }  59  60     for(int k=t; k
       
        = ans) return;        //剪枝  62  63         if(check(bus[k].begin, bus[k].interval)){
    64             int tmp = bus[k].interval;  65  66             for(int i=bus[k].begin; i<60; i+=tmp){        //除去这条线路  67                 sum[i]--;  68                 n--;  69             }  70             dfs(k, num+1);                        //可能的公车路线应从k开始(因为K之前的已不考虑--（1）)， 也不能是K+1，  71 //因为两条公车路线可能时间完全相同  72  73             for(int i=bus[k].begin; i<60; i+=tmp){        //回溯  74                 sum[i]++;  75                 n++;  76             }  77         }  78     }  79 }  80  81 int main(){
    82     int a;  83     scanf("%d", &n);  84     for(int i=0; i
       
      
     

　　

　　

1 (*  2  * 策略二：http://hi.baidu.com/lin791263068/blog/item/7c349de8f5204221279791d3.html  3  *  4  * 关于head 和 tail ：  5  *    因为有一些车辆是同时到站的，而这里是按照时刻来进行深搜的，  6  *    同一时刻可以发出很多车辆。  7  *    head表示这趟线路上有一辆车的条数  8  *    (注：即以该时刻的一辆车为该线路的第一辆车，此时还不知道该线路  9  *    是否只有这一辆车，需按后面的搜索而定，故需tail)， 10  *    tail表示确定为一条线路的条数（即后续的搜索为原来的head[i]后加了一辆车， 11  *    这是该线路就有两辆车，符合条件）。 12  *    最终答案要求每趟线路上至少有两辆车，最后通过head，tail 来检验一下是否满足条件。 13  * 14  *) 15 var 16   head,tail,num:array[0..59] of longint; 17   ans,tot:longint; 18 function check:boolean; 19 var 20   i:longint; 21 begin 22   for i:=0 to 59 do 23   if head[i]>tail[i] then exit(false); 24   exit(true); 25 end; 26 procedure dfs(s:longint); 27 var 28   i,now,gc:longint; 29 begin 30   while (s<60) and (num[s]=0) do inc(s); 31   if s=60 then 32   begin 33     if check and (tot
     
      tail[i] then (*设为第二辆车*) 40     begin 41       gc:=s-i; now:=s+gc; 42       while (now<60) and (num[now]>0) do inc(now,gc); 43       if now>59 then 44       begin 45         now:=s; inc(tail[i]); 46         while now<60 do 47         begin 48           dec(num[now]); 49           inc(now,gc); 50         end; 51         dfs(s); 52         now:=s; dec(tail[i]); 53         while now<60 do 54         begin 55           inc(num[now]); 56           inc(now,gc); 57         end; 58       end; 59     end; 60     if tot+1