蓝桥杯历届试题 大臣的旅费

发表于由
问题描述

很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。

J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入格式

输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数

城市从1开始依次编号，1号城市为首都。

接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）

每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。

输出格式

输出一个整数，表示大臣J最多花费的路费是多少。

样例输入1
5
1 2 2
1 3 1
2 4 5
2 5 4
样例输出1
135
输出格式

大臣J从城市4到城市5要花费135的路费。

注意1:路费实际上就是路径长度＊10+路径的累加  即  a*10+(1+a)*a/2

注意2:最后一个测试用例过大，不用链接保存即超大。

注意3:n－1条路径必然是最小生成树，用找直径算法，即从任意点找最远点，再从最远点找最远点即可。

代码：

  1. #include <iostream>
  2. #include<string>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<vector>
  6. using namespace std;
  7. int n;
  8. int maxn;
  9. int sum;
  10. int visited[100005];
  11. int flag;
  12. #define ni 100005
  13. struct node
  14. {
  15.     int w;
  16.     int num;
  17. };
  18. vector<node>g[ni];
  19. int index;
  20. void dfs(int t)
  21. {
  22.     if(sum>maxn)
  23.     {
  24.         maxn=sum;
  25.         index=t;
  26.     }
  27.     for(int j=0;j<(int)g[t].size();j++)
  28.     {
  29.         node ta = g[t][j];
  30.         if(!visited[ta.num])
  31.         {
  32.                 visited[ta.num]=1;
  33.                 sum+=ta.w;
  34.                 dfs(ta.num);
  35.                 sum-=ta.w;
  36.                 visited[ta.num]=0;
  37.         }
  38.     }
  39. }
  40. int main()
  41. {
  42.     cin>>n;
  43.     for(int i=1;i<=n-1;i++)
  44.     {
  45.         int a,b,c;
  46.         cin>>a>>b>>c;
  47.         node ta,tb;
  48.         ta.num=a;ta.w=c;
  49.         tb.num=b;tb.w=c;
  50.         g[a].push_back(tb);
  51.         g[b].push_back(ta);
  52.     }
  53.     memset(visited, 0, sizeof(visited));
  54.     //flag = 0;
  55.     visited[1] = 1;
  56.     dfs(1);
  57.     memset(visited, 0, sizeof(visited));
  58.    // flag = 0;
  59.     visited[index] = 1;
  60.     dfs(index);
  61.     //cout<<maxn<<endl;
  62.     int cost=0;
  63.     for(int i=1;i<=maxn;i++)
  64.     {
  65.         cost=cost+i+10;
  66.     }
  67.     cout<<cost<<endl;
  68.     return 0;
  69. }

错误样例：

#include<iostream>

using namespace std;

int n = 0;

bool visted[100005];

int cost = 0;

void DFS(int start,int end,int tempcost,int **vx)

{

    if(start == end)

    {

        if(tempcost>cost)

            cost = tempcost;

    }else

    {

        for(int i = 1;i<n+1;i++)

        {

            if(vx[i][start]>=0&&visted[i]==false)

            {

                tempcost += vx[i][start];

                visted[i] = true;

                DFS(i,end,tempcost,vx);

                visted[i] = false;

                tempcost -= vx[i][start];

            }

        }

    }

}

void clear()

{

    for(int i = 0 ; i <100005;i++)

    {

        visted[i] = false;

    }

}

int main()

{

    

    cin>>n;

    int **vx = new int*[n+1];

    for(int i=1;i<n+1;i++)

        vx[i] = new int[n+1];

    for(int i = 1;i<n+1;i++)

    {

        for(int j = 1;j<n+1;j++)

        {

            vx[i][j] = –1;

        }

    }

    for(int i = 0 ; i <n–1;i++)

    {

        int x,y,q;

        cin>>x;

        cin>>y;

        cin>>q;

        vx[x][y]=q;

        vx[y][x]=q;

    }

    int max=0;

    int max_end=0;

    for(int i = 2;i<n+1;i++)

    {

        clear();

        cost=0;

        visted[1]=1;

        DFS(1,i,0,vx);

        if(max<cost)

        {

            cost=max;

            max_end = i;

        }

    }

    for(int i = 1;i<n+1;i++)

    {

        clear();

        cost=0;

        if(max_end!=i)

        {

        visted[max_end]=1;

        DFS(max_end,i,0,vx);

        if(max<cost)

        {

            max=cost;

        }

        }

    }

    cout<<max*10+(max+1)*max/2;

    return 0;

}

发表评论