大臣的旅费

问题描述

很久以前，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的路费。

---

ALgorithm

一共有 n 个点，共 n - 1 条路线，且任意两点之间有路线，无环，因此这是一个树，也是一个无环无向图。

因此就可以使用DFS或BFS进行搜索，或用Floyd算法求多源点之间的最短路（将边的权改为负）。

但是Floyd算法的时间复杂度很高 O(n^3)，只能通过75%的数据，事实上，大约超过 300 个点之后都会运行超时，只是它的测试数据较弱罢了

---

---

AC

首先是Floyd算法：

/*
* 多源点之间的最短距离 
* 还忽略一个问题, 那就是邻接矩阵的大小 
*/
#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;

const int MAX_V = 1009;
const int INF = 1e6;

int e[MAX_V][MAX_V];
int n = 0;

void print(int a[MAX_V][MAX_V])
{
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<'	';
        }
        cout<<'
';
    }        
}

int main()
{
    // Init 放在while(cin)里面出问题,,, 
    for(int i=1;i<=MAX_V;i++)
        for(int j=1;j<=MAX_V;j++){
            if(i == j){
                e[i][j] = 0;
            }
            else{
                e[i][j] = INF;
            }
        }
    while(cin>>n)
    {    
        int a, b, t;
        int ret = 1;
        for(int i=1;i<n;i++){
            cin>>a>>b>>t;
            e[a][b] = e[b][a] = -t;    // 赋负权 
        }
        // print(e);
        // floyd
        // 居然没有 0 ...... 
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    // 非得逼我手算一次才能发现问题所在...(abs) 
                    if(abs(e[i][j]) > abs(e[i][k] + e[k][j])){
                        if(e[i][j] == 0)     // 负权要注意一下 ,手算了一次... 
                            continue;
                        e[i][j] = e[i][k] + e[k][j];
                        ret = min(e[i][j], ret);
                    }    
        // print(e);
        ret = -ret;
        int ans = (11 + (ret+10))*(ret)/2;
        cout<<ans<<endl;
        break;
    }

    return 0;
}

 接下来是深搜：

/*
* 比较典型的图或树的搜索
* 这个图比较稀疏, 邻接表可能会好一点 
* 我们只要搜索度为 1 的点就好, 它一定是起点或者终点
* 因为如果度大于 1 的点是终点的话,一定可以继续走下去 
- 后记 - ：我没想到怎样避免不搜索图中遇到它... 
- 现在有想法了, 如果它是起点,那么 dis = 0 
* 那么它一定还可以继续前进 
* -----------------------------------
* 此外, 还可以用Floyd算法来求多源点之间的最短距离
* 这里的距离是求最长距离，所以赋予其负的权值就 ok 
*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

const int MAX_V = 10009; // 题目没有说最大城市的数量 
int ret = -1;             // 最大花费 
int dis = 0;             // 当前走的距离 
bool book[MAX_V];
int s = 0;
int km = 0;
int loc = 0;

struct edge{
    int to;        // 去的点 
    int len;    // 两点之间的距离 
};

vector<edge> G[MAX_V];

// 搜索起点,从 1 开始找最远的距离 
void finds(int a, int km)
{
    // cout<<a<<endl;
    if(G[a].size() == 1 && km != 0){
        if(km > s){
            loc = a;
            s = km;
        }
    }
    for(int i=0;i<G[a].size();i++){
        if(book[G[a].at(i).to] == true){
            book[G[a].at(i).to] = false; // 标记当前点 
            finds(G[a].at(i).to, km+G[a].at(i).len);
            book[G[a].at(i).to] = true;
        }
    }
}

// 费用最大，即走的路程最多 
void dfs(int a, int dis)
{    
    if(G[a].size() == 1 && dis != 0){ // 到了度为1的点，搜索结束 
        ret = max(dis, ret);
        return;
    } 
    for(int i=0;i<G[a].size();i++){
        if(book[G[a].at(i).to] == true){
            book[G[a].at(i).to] = false; // 标记当前点 
            dfs(G[a].at(i).to, dis+G[a].at(i).len);
            book[G[a].at(i).to] = true;
        }
    }
    
    return;
}

int main()
{
    int n;
    // while(cin>>n)
    cin>>n;
    {
        int go;
        edge E1, E2;
        while(--n)
        {
            cin>>go>>E1.to>>E1.len;
            G[go].push_back(E1);
            E2.to = go; E2.len = E1.len; 
            G[E1.to].push_back(E2);
        }
        memset(book, true, sizeof(book));
        book[1] = false;
        finds(1, 0);
        //cout<<"loc: "<<loc<<endl;
        //cout<<"s: "<<s<<endl;
        memset(book, true, sizeof(book));
        book[loc] = false;
        dfs(loc, 0);
        //cout<<"ret: "<<ret<<endl;
        cout<<((11 + (ret+10))*(ret)/2)<<endl;
    }
    
    return 0;
}
/* 好像是错误的，通过的数据应该是巧合 
edge mx;
mx.len = 0;
int s = 0;
for(int i=1;i<=N;i++){ // 会不会一定经过权值最大的度为1的点？ 
            if(G[i].size() == 1){
                if(G[i][0].len > mx.len){
                    mx = G[i][0];
                    s = i;
                }
            }
        }
*/

 深搜分两次，第一次找起点，第二次找最长路径。就像提示里说的那样......

2019-02-18

21:19:25