(一) 图论
1. 大臣的旅费
很久以前, 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≤n≤1051≤Pi,Qi≤n,
1≤Di≤1000
输入样例:
- 5
- 1 2 2
- 1 3 1
- 2 4 5
- 2 5 4
输出样例:
135
解题思路: 这是一道图论题, 找出最长的一条路径, 然后计算他们的总和, 加入最长的路径为 s:ans=s*10+s*(s+1)/2, 接下来就是求在图中最长的路径
如何找出图中最长的两点间的最长距离?
解法: 在图中任选一个点, 计算出他到其他各点的距离, 找出最远的距离的那个点, 然后再用这个点开始, 计算出他与其他个点之间的距离.
然后找出最远的距离, 即为我们要找的整个图中最远的距离.
代码:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<vector>
- using namespace std;
- typedef long long ll;
- const int N=100100;
- struct node
- {
- int id,w;
- };
- vector<node> f[N];
- int dis[N];
- int n,p,q,d;
- void dfs(int u,int father,int distence)
- {
- dis[u]=distence;
- for(vector<node>::iterator iter=f[u].begin();iter!=f[u].end();iter++)
- {
- if(iter->id!=father)
- dfs(iter->id,u,distence+iter->w);
- }
- }
- int main()
- {
- int i,j;
- cin>>n;
- for(i=0;i<n-1;i++)
- {
- scanf("%d%d%d",&p,&q,&d);
- f[p].push_back({q,d});
- f[q].push_back({p,d});
- }
- dfs(1,-1,0);
- int ans=1;
- for(i=1;i<=n;i++)
- {
- if(dis[i]>dis[ans])
- {
- ans=i;
- }
- }
- dfs(ans,-1,0);
- for(i=1;i<=n;i++)
- {
- if(dis[i]>dis[ans])
- {
- ans=i;
- }
- }
- ll s=dis[ans];
- cout<<s*10+s*(s+1)/2<<endl;
- return 0;
- }
(二) 单链表
实现一个单链表, 链表初始为空, 支持三种操作:
(1) 向链表头插入一个数;
(2) 删除第 k 个插入的数后面的数;
(3) 在第 k 个插入的数后插入一个数
现在要对该链表进行 M 次操作, 进行完所有操作后, 从头到尾输出整个链表.
注意: 题目中第 k 个插入的数并不是指当前链表的第 k 个数. 例如操作过程中一共插入了 n 个数, 则按照插入的时间顺序, 这 n 个数依次为: 第 1 个插入的数, 第 2 个插入的数,... 第 n 个插入的数.
输入格式
第一行包含整数 M, 表示操作次数.
接下来 M 行, 每行包含一个操作命令, 操作命令可能为以下几种:
(1) "H x", 表示向链表头插入一个数 x.
(2) "D k", 表示删除第 k 个输入的数后面的数 (当 k 为 0 时, 表示删除头结点).
(3) "I k x", 表示在第 k 个输入的数后面插入一个数 x(此操作中 k 均大于 0).
输出格式
共一行, 将整个链表从头到尾输出.
数据范围
1≤M≤100000 所有操作保证合法.
输入样例:
- 10
- H 9
- I 1 1
- D 1
- D 0
- H 6
- I 3 6
- I 4 5
- I 4 5
- I 3 4
- D 6
输出样例:
6 4 6 5
代码:
- #include<iostream>
- #include<algorithm>
- using namespace std;
- const int N=100010;
- int head,index,n[N],ne[N];
- void init()
- {
- head=-1;
- index=0;
- }
- void add_head(int e)
- {
- n[index]=e;
- ne[index]=head;
- head=index;
- index++;
- }
- void add(int k,int e)
- {
- n[index]=e;
- ne[index]=ne[k];
- ne[k]=index;
- index++;
- }
- void del(int k)
- {
- ne[k]=ne[ne[k]];
- }
- int main()
- {
- int m,i,j,x,k;
- cin>>m;
- char c;
- init();
- for(i=0;i<m;i++)
- {
- cin>>c;
- if(c=='H')
- {
- cin>>x;
- add_head(x);
- }
- else if(c=='D')
- {
- cin>>k;
- if(!k)
- head=ne[head];
- else
- del(k-1);
- }
- else if(c=='I')
- {
- cin>>k>>x;
- add(k-1,x);
- }
- }
- for(i=head;i!=-1;i=ne[i])
- cout<<n[i]<<" ";
- cout<<endl;
- return 0;
- }
来源: https://www.cnblogs.com/xiaofengzai/p/12248149.html