HPU 暑期集训 Day 9
今天主要讲了树的直径，是用bfs和dfs实现的，但是我的dfs，emm，一言难尽，所以我只用了bfs。
关于今天刷题遇到的主要的知识，请去这里查看。
---------->戳这里
Labyrinth
Description:
The northern part of the Pyramid contains a very large and complicated labyrinth. The labyrinth is divided into square blocks, each of them either filled by rock, or free. There is also a little hook on the floor in the center of every free block. The ACM have found that two of the hooks must be connected by a rope that runs through the hooks in every block on the path between the connected ones. When the rope is fastened, a secret door opens. The problem is that we do not know which hooks to connect. That means also that the neccessary length of the rope is unknown. Your task is to determine the maximum length of the rope we could need for a given labyrinth.
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers C and R (3 <= C,R <= 1000) indicating the number of columns and rows. Then exactly R lines follow, each containing C characters. These characters specify the labyrinth. Each of them is either a hash mark (#) or a period (.). Hash marks represent rocks, periods are free blocks. It is possible to walk between neighbouring blocks only, where neighbouring blocks are blocks sharing a common side. We cannot walk diagonally and we cannot step out of the labyrinth.
The labyrinth is designed in such a way that there is exactly one path between any two free blocks. Consequently, if we find the proper hooks to connect, it is easy to find the right path connecting them.
Output
Your program must print exactly one line of output for each test case. The line must contain the sentence "Maximum rope length is X." where Xis the length of the longest path between any two free blocks, measured in blocks.
Sample Input
2
3 3
###
#.#
###
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######
Sample Output
Maximum rope length is 0.
Maximum rope length is 8.
Hint
Huge input, scanf is recommended.
If you use recursion, maybe stack overflow. and now C++/c 's stack size is larger than G++/gcc
Problem solving:
这一题是最简单的求树的直径的题，bfs两次即可，注意虽然第一次开始查找的位置可以是任意的，但是第二次开始的位置应该是第一次查找到最后的那个位置，还有就是两个bfs之间不要忘了memset。
Code:
#include
#include
#include
#include
using namespace std;
int dis[1005][1005];
int vis[1005][1005];
char s[1005][1005];
int d[4][2]={1,0,0,1,-1,0,0,-1};
struct node{
int x,y;
};
int n,c,r,sx,sy;
int bfs(int x,int y)
{
node now,mid;
queue que;
now.x=x;now.y=y;
que.push(now);
vis[x][y]=1;dis[x][y]=0;
while(!que.empty())
{
now=que.front();
que.pop();
for(int i=0;i<4;i++)
{
mid.x=now.x+d[i][0];
mid.y=now.y+d[i][1];
if(mid.x=r||mid.y=c||s[mid.x][mid.y]=='#'||vis[mid.x][mid.y]) continue;
vis[mid.x][mid.y]=1;
dis[mid.x][mid.y]=dis[now.x][now.y]+1;
que.push(mid);
}
}
}
int main()
{
scanf("%d",&n);
while(n--)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
scanf("%d %d",&c,&r);
int flag=0;
for(int i=0;i scanf("%s",s[i]);
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(s[i][j]=='.')
{
sx=i,sy=j;
flag=1;
break;
}
if(flag) break;
}
}
bfs(sx,sy);int px=0;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(dis[i][j]>px)
{
sx=i;
sy=j;
px=dis[i][j];
}
}
}
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
bfs(sx,sy);
int ans=0;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
ans=max(ans,dis[i][j]);
}
}
printf("Maximum rope length is %d.\n",ans);
}
}Cow Marathon
Description:
After hearing about the epidemic of obesity in the USA, Farmer John wants his cows to get more exercise, so he has committed to create a bovine marathon for his cows to run. The marathon route will include a pair of farms and a path comprised of a sequence of roads between them. Since FJ wants the cows to get as much exercise as possible he wants to find the two farms on his map that are the farthest apart from each other (distance being measured in terms of total length of road on the path between the two farms). Help him determine the distances between this farthest pair of farms.
有n个农田和m条路，以及每条路的方向（方向在这道题中没有用），求最长的一条路，也就是两点间的最大距离，即树的直径.
Input
- Lines 1.....: Same input format as "Navigation Nightmare".
Output
- Line 1: An integer giving the distance between the farthest pair of farms.
Sample Input
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
Sample Output
52
Hint
The longest marathon runs from farm 2 via roads 4, 1, 6 and 3 to farm 5 and is of length 20+3+13+9+7=52.
Problem solving:
这道题就是一道带权的无向图求树的最大直径。
直接套模板即可。
Code:
#include
#include
#include
#include
#include
using namespace std;
int a,b,c,ans,n,m;
const int maxn = 1e5+10;
int vis[maxn],dis[maxn];
char s;
vector > v[maxn];
int bfs(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
vis[x]=1;
int point=0;
queue q;
q.push(x);
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)
{
ans=dis[x];
point=x;
}
pair mid;
for(int i=0;i<v[x].size();i++)
{
mid=v[x][i];
if(!vis[mid.first])
{
vis[mid.first]=1;
dis[mid.first]=dis[x]+mid.second;
q.push(mid.first);
}
}
}
return point;
}
int main()
{
cin>>n>>m;
while(m--)
{
cin>>a>>b>>c>>s;
v[a].push_back(make_pair(b,c));
v[b].push_back(make_pair(a,c));
}
ans=0;
int point=bfs(1);
ans=0;
bfs(point);
cout<<ans<<endl;
return 0;
}Roads in the North
Description:
Building and maintaining roads among communities in the far North is an expensive business. With this in mind, the roads are build such that there is only one route from a village to a village that does not pass through some other village twice.
Given is an area in the far North comprising a number of villages and roads among them such that any village can be reached by road from any other village. Your job is to find the road distance between the two most remote villages in the area.
The area has up to 10,000 villages connected by road segments. The villages are numbered from 1.
Input
Input to the problem is a sequence of lines, each containing three positive integers: the number of a village, the number of a different village, and the length of the road segment connecting the villages in kilometers. All road segments are two-way.
Output
You are to output a single integer: the road distance between the two most remote villages in the area.
Sample Input
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
Sample Output
22
Problem solving:
同B，直接套模板即可。这里是输入组数不确定，所以直接while(cin)即可。
Code:
#include
#include
#include
#include
#include
using namespace std;
int a,b,c,ans;
const int maxn = 1e5+10;
int vis[maxn],dis[maxn];
vector > v[maxn];
int bfs(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
vis[x]=1;
int point=0;
queue q;
q.push(x);
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)
{
ans=dis[x];
point=x;
}
pair mid;
for(int i=0;i<v[x].size();i++)
{
mid=v[x][i];
if(!vis[mid.first])
{
vis[mid.first]=1;
dis[mid.first]=dis[x]+mid.second;
q.push(mid.first);
}
}
}
return point;
}
int main()
{
while(cin>>a>>b>>c)
{
v[a].push_back(make_pair(b,c));
v[b].push_back(make_pair(a,c));
}
ans=0;
int point=bfs(1);
ans=0;
bfs(point);
cout<<ans<<endl;
return 0;
}Computer
Description:
一所学校不久前买了第一台电脑（所以这台电脑的ID是1）。近年来，学校购买了N-1新电脑。每台新电脑都连接到一台先前安装的电脑上。学校的管理人员担心网络运行缓慢，希望知道第i台计算机需要发送信号的最大距离si（即到最远计算机的电缆长度）。您需要提供此信息。
提示：示例输入与此图对应。从图中，你可以看到计算机4离1最远，所以s1=3。计算机4和5是距离2最远的，所以s2=2。计算机5是离3最远的，所以s3=3。我们也得到了s4=4，s5=4。
输入
输入文件包含多组测试样例。在每组样例中，第一行中都有自然数n（n<=10000），然后是（n-1）行，其中包含对计算机的描述。第i行包含两个自然数-第i计算机所连接的计算机和用于连接的电缆长度。电缆总长度不超过1e9。输入行中的数字用空格分隔。
输出
对于每组样例，输出n行。第i行第i台计算机的到其他计算机的最大长度Si（1<=i<=n）。
样例输入
5
1 1
2 1
3 1
1 1
样例输出
3
2
3
4
4
提示
示例输入与此图对应。从图中，你可以看到计算机4离1最远，所以s1=3。计算机4和5是距离2最远的，所以s2=2。计算机5是离3最远的，所以s3=3。我们也得到了s4=4，s5=4。
Problem solving:
这道题应该是今天最难的题了。一开始毫无思路，但是后来听了学长一句话。离某个点最远的一定是树的直径的端点。我们第一次bfs结束时的点是这个树的两个端点之一，再以这个端点就行bfs结束的时候就到了另外一个端点，而且我们在查找的过程中使用的dis数组就是当前位置距离将要到达的！！端点！！的距离，所以就在bfs一次，与上一次得到的距离去max最大值即可。总结一下就是三次bfs。
Code:
#include
#include
#include
#include
#include
using namespace std;
const long long maxn=1e5;
long long n,a,b,ans;
long long vis[maxn],dis[maxn],dis2[maxn];
vector > v[maxn];
long long bfs(long long x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
ans=0;
queue q;
q.push(x);
vis[x]=1;
long long point;
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)
{
ans=dis[x];
point=x;
}
pair mid;
for(long long i=0;i<v[x].size();i++)
{
mid=v[x][i];
if(!vis[mid.first])
{
vis[mid.first]=1;
dis[mid.first]=dis[x]+mid.second;
q.push(mid.first);
}
}
}
return point;
}
int main()
{
while(cin>>n)
{
memset(v,0,sizeof(v));
for(long long i=2;i<=n;i++)
{
cin>>a>>b;
v[a].push_back(make_pair(i,b));
v[i].push_back(make_pair(a,b));
}
long long point=bfs(1);
long long next=bfs(point);
for(long long i=1;i dis2[i]=dis[i];
bfs(next);
for(long long i=1;i
{
cout<<max(dis2[i],dis[i])<<endl;;
}
}
}Farthest Nodes in a Tree
Description:
Given a tree (a connected graph with no cycles), you have to find the farthest nodes in the tree. The edges of the tree are weighted and undirected. That means you have to find two nodes in the tree whose distance is maximum amongst all nodes.
Input
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with an integer n (2 ≤ n ≤ 30000) denoting the total number of nodes in the tree. The nodes are numbered from 0 to n-1. Each of the next n-1 lines will contain three integers u v w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 10000) denoting that node u and v are connected by an edge whose weight is w. You can assume that the input will form a valid tree.
Output
For each case, print the case number and the maximum distance.
Sample Input
2
4
0 1 20
1 2 30
2 3 50
5
0 2 20
2 1 10
0 3 29
0 4 50
Sample Output
Case 1: 100
Case 2: 80
Problem solving:
同BC，直接套模板就行。然后就是输出格式的控制
Code:
#include
#include
#include
#include
const int maxn= 1e5+10;
using namespace std;
int dis[maxn],ans;
bool vis[maxn];
vector > v[maxn];
int bfs(int x)
{
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
queue que;
que.push(x);vis[x]=1;
int point=0;
while(!que.empty())
{
int f=que.front();
que.pop();
if(dis[f]>ans)
{
ans=dis[f];
point=f;
}
pair t;
for(int i=0;i<v[f].size();i++)
{
t=v[f][i];
if(vis[t.first]==0)
{
vis[t.first]=1;
dis[t.first]=dis[f]+t.second;
que.push(t.first);
}
}
}
return point;
}
int main()
{
int n,m,x,y,z,flag=0;
cin>>n;
while(n--)
{
memset(v,0,sizeof(v));
cin>>m;
for(int i=1;i<m;i++)
{
cin>>x>>y>>z;
v[x].push_back(make_pair(y,z));
v[y].push_back(make_pair(x,z));
}
ans=0;
int point=bfs(1);
ans=0;
bfs(point);
printf("Case %d: %d\n",++flag,ans);
}
}51nod 2602 树的直径
Description:
一棵树的直径就是这棵树上存在的最长路径。现在有一棵n个节点的树，现在想知道这棵树的直径包含的边的个数是多少？
如图所示的数据，这棵树的直径为(1-2-3-6-9)这条路径，包含的边的个数为4，所以答案是4。
输入
第1行：一个整数n，表示树上的节点个数。(1<=n<=100000)
第2-n行：每行有两个整数u,v,表示u与v之间有一条路径。(1<=u,v<=n)
输出
输出一个整数，表示这棵树直径所包含的边的个数。
输入样例
10
1 2
2 3
3 4
3 5
3 6
3 7
3 10
6 8
6 9
输出样例
4
Problem solving:
求树的直径的模板题。不过无权值。
Code:
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e5+10;
int dis[maxn],ans,vis[maxn],n,a,b;
vector v[maxn];
int bfs(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
queue q;
q.push(x);
vis[x]=1,dis[x]=0;
int point;
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)
{
ans=dis[x];
point=x;
}
for(int i=0;i<v[x].size();i++)
{
if(!vis[v[x][i]])
{
vis[v[x][i]]=1;
dis[v[x][i]]=dis[x]+1;
q.push(v[x][i]);
}
}
}
return point;
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
ans=0;
int point=bfs(1);
ans=0;
bfs(point);
cout<<ans<<endl;
}模板
上面有三道题我都直接说得套模板。那么求树的直径的模板是什么呢？这里只写上带权的吧，不带权的可以类比得出。或者去这里看：---------->戳这里
在这里我结合代码想详细的分析一下这个模板。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int a,b,c,ans;
const int maxn = 1e5+10;
int vis[maxn],dis[maxn];//dis数组储存的就是当前点能向一个确定的方向走的最大的距离。vis就是一个标记数组防止重复访问。
vector<pair<int,int> > v[maxn]; //用来存图，可以看成是一个二维数组,因为是有权值的，所以在vector中套用了一个pair
int bfs(int x)
{
memset(vis,0,sizeof(vis));//因为要进行多次bfs，所以每次都要清空一下数组
memset(dis,0,sizeof(dis));
vis[x]=1;//已经访问过的节点标记为1
int point=0;//用来储存当前所能走到的最远的点
queue<int> q;//用来实现bfs的队列
q.push(x);
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)//如果当前点能走的最大的步数大于ans，ans初始为0，如果大于就更新ans和point的值
{
ans=dis[x];
point=x;
}
pair<int,int> mid;
for(int i=0;i<v[x].size();i++)//对v[x]中的每一个元素进行bfs
{
mid=v[x][i];
if(!vis[mid.first])//没访问过就继续
{
vis[mid.first]=1;//标记成已经访问过的
dis[mid.first]=dis[x]+mid.second;//这个点的能走的最大的距离多了一个dis[x]
q.push(mid.first);//放进队列以进行bfs
}
}
}
return point;//把当前走到的最远的点返回
}
int main()
{
while(cin>>a>>b>>c)
{
v[a].push_back(make_pair(b,c));//存图
v[b].push_back(make_pair(a,c));
}
ans=0;//初始化
int point=bfs(1);
ans=0;
bfs(point);//第二次以某一端点位起点的bfs
cout<<ans<<endl;
return 0;
}
失业啃老第二年，熬夜玩手机中。。