很久以前,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 2 2
1 3 1
2 4 5
2 5 4
大臣J从城市4到城市5要花费135的路费。
按题目提示,我用深搜写了一下,不过只有75分,最后一个测试样例超时了.
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <algorithm> 8 #define INF 0x3f3f3f3f 9 #define zero 1e-7 10 11 using namespace std; 12 typedef long long ll; 13 const ll mod=1e9+7; 14 const ll max_n=1e6+7; 15 16 struct node { 17 int p, q, d; 18 }mp[max_n]; 19 20 bool vise[max_n]={false};//标记边 21 bool visv[max_n]={false};//标记点 22 int n, maxd=0; 23 24 void dfs(int s, int sum) {//上一条边的末端点的编号、总路程 25 visv[s]=true; 26 bool flag=false;//标记是否有下一条边,即s是否为树的叶子结点 27 for(int i=0; i<n-1; i++) { 28 if(!vise[i]) { 29 vise[i]=true; 30 if(mp[i].p==s && !visv[mp[i].q]) { 31 dfs(mp[i].q, sum+mp[i].d); 32 flag=true; 33 } 34 if(mp[i].q==s && !visv[mp[i].p]) { 35 dfs(mp[i].p, sum+mp[i].d); 36 flag=true; 37 } 38 vise[i]=false; 39 } 40 } 41 visv[s]=false; 42 if(!flag) maxd=max(maxd, sum); 43 } 44 45 int main() { 46 int p, q, d; 47 int ans; 48 cin>>n; 49 for(int i=0; i<n-1; i++) { 50 cin>>p>>q>>d; 51 mp[i].p=p; 52 mp[i].q=q; 53 mp[i].d=d; 54 } 55 for(int i=0; i<n-1; i++) { 56 if(!visv[mp[i].p]) { 57 dfs(mp[i].p, 0); 58 } 59 if(!visv[mp[i].q]) { 60 dfs(mp[i].q, 0); 61 } 62 } 63 ans=maxd*10+maxd*(1+maxd)/2; 64 cout<<ans<<endl; 65 return 0; 66 }
一时间不知道要怎么改,就百度了一下,然后通过这位博主提供的如下思路,一点就通,于是把代码改了一下,果然过了.
解题思路:由于这道题的特殊要求,不难发现,每个点到点1的路径是唯一的,而求出任意两个点的最大距离,可以转化为求两个距离点1最远的点,如果这两个点的距离大于刚刚求得的两个最大值,那这个距离便是所求的值,否则便取到点1的最远距离.
最小生成树任意两点间的路径都是唯一的,但是为什么一棵树距离最远的两个点的距离可以这样求,我还是没太明白.
以下是AC代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <algorithm> 8 #define INF 0x3f3f3f3f 9 #define zero 1e-7 10 11 using namespace std; 12 typedef long long ll; 13 const ll mod=1e9+7; 14 const ll max_n=1e6+7; 15 16 struct node { 17 int p, q, d; 18 }mp[max_n]; 19 20 bool vise[max_n]={false};//标记边 21 bool visv[max_n]={false};//标记点 22 int n, maxd=0, maxv; 23 24 void dfs(int s, int sum) {//上一条边的末端点的编号、总路程 25 visv[s]=true; 26 bool flag=false;//标记是否有下一条边,即s是否为树的叶子结点 27 for(int i=0; i<n-1; i++) { 28 if(!vise[i]) { 29 vise[i]=true; 30 if(mp[i].p==s && !visv[mp[i].q]) { 31 dfs(mp[i].q, sum+mp[i].d); 32 flag=true; 33 } 34 if(mp[i].q==s && !visv[mp[i].p]) { 35 dfs(mp[i].p, sum+mp[i].d); 36 flag=true; 37 } 38 vise[i]=false; 39 } 40 } 41 visv[s]=false; 42 if(!flag && sum>maxd) { 43 maxd=sum; 44 maxv=s; 45 } 46 } 47 48 int main() { 49 int p, q, d; 50 int ans; 51 cin>>n; 52 for(int i=0; i<n-1; i++) { 53 cin>>p>>q>>d; 54 mp[i].p=p; 55 mp[i].q=q; 56 mp[i].d=d; 57 } 58 dfs(1, 0);//搜索离1最远的点maxv 59 dfs(maxv, 0); //搜索离maxv最远的点 60 ans=maxd*10+maxd*(1+maxd)/2; 61 cout<<ans<<endl; 62 return 0; 63 }