小黑

用户名：20190341315

访问量：8021

签　名：

菜！是真的菜，水题还做不全乎！菜。

等　　级
排　　名	126
经　　验	7718
参赛次数	8
文章发表	25
年　　龄	0
在职情况	学生
学　　校	郑州商学院
专　　业	计算机科学与技术

　　自我简介：

C/C++初学菜鸟

TA的其他文章

蓝桥杯算法提高VIP-统计单词数-题解（C语言代码）
浏览：851

[出圈]-题解（C语言代码）
浏览：411

树查找-题解（C++代码）
浏览：343

你可能喜欢

蓝桥杯2013年第四届真题-大臣的旅费-题解（C++代码）

　　作者: 小黑　　　　发表时间：2020-12-07 19:39:05 浏览：286　|　评论：0　

原题链接：蓝桥杯2013年第四届真题-大臣的旅费

#### 这一题真是搞人心态,用邻接矩阵居然爆栈
#### 那就原始邻接表和vector邻接表;
```javascript
#include<bits/stdc++.h>
using namespace std;
#define N 100000
typedef struct st{
	int v;//结点编号 
	int w;//权值 
	struct st *nx;//结点指针(指向下一个结点) 
}ll,*link;//类型 
struct sx{
	ll *next;//表头后面跟的结点 
}s[N];//邻接表的表头 
int n;
int book[N]={0};
int str=0;//记录两次最远距离 
int max1=-1;//最大权值 
void dfs(int x,int k)
{//x：结点编号; k：权值累加和;  
	if(k>max1)
	{
		max1=k;//记录最大权值 
		str=x;//记录访问最远的结点编号 
	}
	link p;
	p=s[x].next;
	while(p)
	{
		if(book[p->v]==0)
		{
			book[p->v]=1;//访问后标记 
			dfs(p->v,k+p->w);
			book[p->v]=0;//取消标记供寻走到尽头返回后再使用 
		}
		p=p->nx;
	}
	return;
}
/*
5 
1  2  2 
1  3  1 
2  4  5 
2  5  4 
*/
int main()
{
	int w,sum=0;
	cin>>n;
	link p;
	int x,y;
	for(int i=1;i<=n;i++)
	{
		s[i].next=0;
	}
	for(int i=1;i<=n-1;i++)
	{//建立邻接表,这是个无向图,需要两部分
		scanf("%d%d%d",&x,&y,&w);
		int th=x;
		p=new ll;
		p->v=y;
		p->w=w;
		p->nx=s[th].next;
		s[th].next=p;
	/*********有向表,下面就不用写了**********/ 
		th=y;
		p=new ll;
		p->v=x;
		p->w=w;
		p->nx=s[th].next;
		s[th].next=p;
	}
	book[1]=1;
	dfs(1,0);//从结点1,权值为0开始,；
	//前面的全局变量str记录从结点能到达最远的结点 
	memset(book,0,sizeof(book));//置0，供下一个dfs使用 
	book[str]=1;
	dfs(str,0);//从结点str,权值为0开始,
	//cout<<"str = "<<str<<endl;
	sum=max1*10+max1*(max1+1)/2;
	cout<<sum<<endl;
	return 0;
}
```
### vector建表
```javascript
#include<bits/stdc++.h>//vecotr构造邻接表 
using namespace std;
#define N 100000
struct st{
    int to;//结点编号 
    int w;//权值 
};//类型 
vector<st> s[N];
int n;
int book[N]={0};
int str=0;//记录两次最远距离 
int max1=-1;//最大权值 
void dfs(int x,int k)
{//x：结点编号; k：权值累加和;  
    if(k>max1)
    {
        max1=k;//记录最大权值 
        str=x;//记录访问最远的结点编号 
    }
    vector<st>::iterator it;
    //迭代器法 
    /*it=s[x].begin();//结点x的邻接的第一个结点 
    while(it!=s[x].end())//到达容器的尾部 
    {
    	if(book[it->to]==0)
    	{
    		book[it->to]=1;
    		dfs(it->to,k+it->w);
    		book[it->to]=0;
		}
		it++;
	}*/
	st t;
	//下标法
	for(int i=0;i<s[x].size();i++) 
	{
		t=s[x][i];
		if(book[t.to]==0)
		{
			book[t.to]=1;
    		dfs(t.to,k+t.w);
    		book[t.to]=0;
		}
	}
    return;
}
void add(int from,int to,int w)//链接结点 
{
	st t;
	t.to=to;
	t.w=w;
	s[from].push_back(t);//入栈
}
/*
5 
1  2  2 
1  3  1 
2  4  5 
2  5  4 
*/
int main()
{
    int w,sum=0;
    cin>>n;
    int x,y;
    for(int i=1;i<=n;i++)
    {
        s[i].clear();
    }
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);//建表，链接结点
        add(y,x,w);
    }
    book[1]=1;
    dfs(1,0);//从结点1,权值为0开始,；
    //前面的全局变量str记录从结点能到达最远的结点 
    memset(book,0,sizeof(book));//置0，供下一个dfs使用 
    book[str]=1;
    dfs(str,0);//从结点str,权值为0开始,
    //cout<<"str = "<<str<<endl;
    sum=max1*10+max1*(max1+1)/2;
    cout<<sum<<endl;
    return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

小黑

TA的其他文章

你可能喜欢

C语言训练-求车速（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蓝桥杯2013年第四届真题-大臣的旅费-题解（C++代码）

评论区

精彩推荐

C语言训练-大、小写问题（C语言代码）

简单的for循环

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

盐水的故事（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

小黑

TA的其他文章

你可能喜欢

C语言训练-求车速 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蓝桥杯2013年第四届真题-大臣的旅费-题解（C++代码）

评论区

精彩推荐

C语言训练-大、小写问题 （C语言代码）

简单的for循环

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

盐水的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

C语言训练-求车速（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

C语言训练-大、小写问题（C语言代码）

盐水的故事（C语言代码）

C二级辅导-等差数列（C语言代码）