POJ - 1167 ---dfs进阶题

小咪咪 2023-08-17 16:26 99阅读 0赞

## The Buses ##

[POJ - 1167][]

题意：小明在站口M记录这一个小时车子到站的时间，判断至少有多少种车子经过的线路？ 每辆车至少要经过两次

如果两辆车子的线路是相同的，那么其时间间隔也是相同的

如果两辆车子的线路是不同的，那么其时间间隔也可能是相同的

我们简化问题：给了n个数(a1,a2,..an)，at=ai+t\*k(k为0,1,2,(59-ai)/t) --- at=ai,at=ai+k, at=ai+k\*2,...直到at的值<59      求最少需要多少个这样的t值能使a1到an这些数都只被取到一次   另外k必须能取0,1(因为每辆车至少出现两次，所以at至少有两个值 k=0,1)

题意第二种表达：  你记录了\[0, 59\]这个时间段内到达你所在站牌的所有公交的到这个站牌的时间  对于每路公交

1. 同一路公交的到站时间间隔是相同的

2. 每路公交在这个时间段至少到达两次

3. 最多有17路公交

4. 两个不同路的公交的第一次到站时间和到站时间间隔都可能是相同滴

5. 你在这个时间段内的记录是完整的

求最少用多少路公交可以让你的记录合法

由于每路公交至少到站两次  那么第一次到站时间是肯定小于30的  而且到站时间间隔肯定要大于第一次到站的时间  那么可以根据你的记录生成所有可能合法的公交线路   最后dfs找出最少的公交线路  使这些线路刚好完全覆盖你的记录  注意dfs过程中的剪枝

搜索。预处理出所有可能存在的公交线路，然后DFS，看选用其中的哪些可以正好使用到数据中的所有车各一次，且选用的线路最少。

剪枝1：由于这一小时里一种车至少来两次，所以只有30分以前来的才可能是始发车

剪枝2：对所有可能的公交线路按车停靠次数大小排序，如果当前选用线路数加上“剩余没安排的车除以当前线路需要的车”（即估计需要线路数）比答案大，剪枝

input:

17
    0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

output:

0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
     我们可以看到只需要三种： 车子在0点开 时间间隔为13

车子在3点开   时间间隔为12

车子在5点开   时间间隔为8

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int ct[60];//表示第i分钟到达的车数
    int n,ans,tp;//车数  答案   总备选线路数目
    struct node{
        int s,j,t;//第一次到达时间  发车间隔  需要车数--该路线从发车到终点需要出现的次数
    }p[301];
    int cmp(node a,node b){
        return a.t>b.t;
    }
    bool test(int s,int t)//起始时间  间隔时间
    {
        for(int i=s;i<60;i+=t)
            if(ct[i]==0)//表示没有车到达   说明这种情况不合理
            return false;
        return true;
    }
    
    void dfs(int t,int now)  //从第t条线路开始匹配  用了now条线路
    {
        int i,j,k,tmp;
        if(n==0)//车子全部假设完  剩余车数为0
        {
            if(now<ans)  ans=now;//路线数目
            cout<<"ans="<<ans<<endl;
            cout<<"起始时间："<<p[t].s<<" 间隔： "<<p[t].j<<endl;
            return;
        }
        for(i=t;i<=tp&&p[i].t>n;i++)//找到合适路线，排除需要车数比剩余车数大的线路
        ;
        for(k=i;k<=tp;k++)//tp 总备选路线
        {
            if(now+n/p[k].t>=ans)  return;
            if(test(p[k].s,p[k].j))
            {
                tmp=p[k].j;
                for(j=p[k].s;j<60;j+=tmp){
                    ct[j]--;
                    n--;
                }
                dfs(k,now+1);
                for(j=p[k].s;j<60;j+=tmp){
                    ct[j]++;
                    n++;
                }
            }
        }
    }
    int main()
    {
        scanf("%d",&n);
        int i,j,a;
        for(i=1;i<=n;i++){
            scanf("%d",&a);
            ct[a]++;
        }
        tp=0;
        for(i=0;i<=29;i++)//记录前30分钟首发车时间
        {
            if(ct[i]!=0){
            for(j=i+1;j<=59-i;j++)//发车间隔
            if(test(i,j)){
                tp++;
                p[tp].s=i;
                p[tp].j=j;
                p[tp].t=1+(59-i)/j;
            }
            }
        }
        sort(p+1,p+tp+1,cmp);
        ans=17;
        dfs(1,0);
        printf("%d",ans);
    }

转载于:https://www.cnblogs.com/Aiahtwo/p/11323482.html

[POJ - 1167]: https://cn.vjudge.net/problem/17627/origin