qq_27279883
qq_27279883
采纳率0%
2016-06-23 03:06 阅读 2.9k

回溯法与分支限界法解算法问题,求完整c或c++程序

20

题目2:在GSM通信系统中,为了避免相邻基站之间的干扰要求相邻的基站之间不能采用相同的频率来进行通信。 由于频率资源有限,因此就要求基站所占用的频率资源越少越好。

输入要求:

输入包含某地区的基站之间的相邻情况。输入的第一行为一个整数n,表示有多少个邻接信息。后面的n行每一行包含一个邻接关系,每一行的形式如下:

A:BCDH

其中A 表示某给基站的名称,:后的每一个字母都表示一个基站的名称,表示与A相邻的基站,基站数量在1~26之间,分别对应1~26个字母。如果某个基站没有相邻的基站,则形式如下:

B:

表示没有与基站B相邻的基站。

输出要求:

输出只有一行,一个整数,也就是需要的最少的频率数。

样例输入:

4

A:BCD

B:ACD

C:ABD

D:ABC

样例输出:

4

题目3:给定一个自然数N,0和M各不同的十进制数字X1,X2,……,XM, 找出由这些数字所构成的正整数中N的倍数最小的正整数,设该正整数不超过232-1。

输入要求:

输入的第一行有两个整数,分别为该自然数N和数字的个数M,第2行有M个数字( 0),数字之间用空格隔开。

输出要求:

输出一行为由这些数字所组成的该自然数的最小倍数,数字可重复使用。如果不存在这样的数,则输出0.

样例输入:

22 3

7 0 1

样例输出:

110

题目4:某商人希望到某地旅游,他选择了几个必须的旅游城市,并绘制处理各城市之间的线路。这些线路都是可以双向通行的,也就是从城市ai能到达bi,也可以从bi回到ai,且路程di相同。现他希望旅游完所有必须旅游的城市,且希望所旅行的线路最短。

输入要求:

输入的第一行有两个整数n和k (2 <= n <= 50000, 1 <= k <= n), 分别表示城市的数量以及第一个出发的城市。其后的n-1行表示城市之间的距离,用ai, bi,和di分别表示相连接的城市的编号以及城市之间的距离。接下来的一行表示他希望旅行的城市的数量,最后一行表示他希望旅行的城市的编号,用空格隔开。

输出要求:

输出一个整数,占1行,表示从第一个城市出发旅行完所有必须旅行的城市所需要的最短路径。

样例输入:

4 2

1 2 1

4 2 2

2 3 3

2

1 3

样例输出:

5

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

2条回答 默认 最新

  • tao6xiao T_Lucifer 2016-06-24 08:00

    同学 你的算法课这学期挂了

    点赞 评论 复制链接分享
  • weixin_46396987 至善之剑 2021-06-22 09:28

    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <sstream>
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <string>
    #include <ctime>
    #define fur(i,a,b) for(int i=(a);i<=(b);i++)
    #define furr(i,a,b) for(int i=(a);i>=(b);i--)
    #define cl(a) memset((a),0,sizeof(a))
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair <int, int> pii;
    const int inf = 0x3f3f3f3f;
    const double eps = 1e-8;
    const int mod =  1000000007;
    const double pi = acos(-1.0);
    const int N = 1010;
    int n;
    int neighbor[N][N];
    int color[N];
    int color_num = 0;
    void Backtrack(int t);
    char record[N];
    bool color_ok(int i, int num);
    int main()
    {
     
        while (scanf("%d\n", &n) !=EOF)
        {
            for (int i = 0; i < n; i++)
            {
                scanf("%s",record);
                for (int j = 2; record[j] != 0; j++)
                {
                    neighbor[i][record[j] - 'A'] = 1;
                }
            }
            Backtrack(0);
        }
        return 0;
    }
     
    bool color_ok(int i, int num)
    {
        for (int j = 0; j < n; j++)
        {
            if (neighbor[i][j]==1)
            if (color[j] == num)
                return false;
        }
        return true;
    }
    void Backtrack(int t)
    {
        if (t>=n)
        {
            printf("%d\n", color_num);
            return;
        }
        else
        {
            int i = 1;
            for (; i <= t; i++) {
                color[t] = i;
                if (color_ok(t, i))
                {
                    Backtrack(t + 1);
                    return;
                }
            }
                color[t] = i;
                if (color_ok(t,i))
                {
                    color_num++;
                    Backtrack(t + 1);
                    return;
                }
        }
    }

    点赞 评论 复制链接分享

相关推荐