昨晚的题，两道编程第一道是求冰雹猜想收敛次数最大的数，一直以为有规律可找，后来发现其实收敛的很快，暴力求解就完事了。
第二道咋一看以为二叉树，后来发现就是一棵树，本质是求树上两个节点间的距离，所以bfs即可，求亲密距离时边权为1，求辈分距离时边权是父到子为1，子到父为-1。
第二题的AC代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct Node
{
int v, w;
Node(int vv, int ww): v(vv), w(ww){}
};
int main()
{
int n, p1, p2;
cin >> n >> p1 >> p2;
vector<vector<Node>> graph(n);
int u, v;
for (int i = 1; i < n; i++){
cin >> u >> v;
graph[u].push_back(Node(v, 1));
graph[v].push_back(Node(u, -1));
}
int qm = 0, bf = 0;
queue<Node> que;
que.push(Node(p1, 0));
vector<int> vis(n+1, 0);
while (!que.empty()){
Node now = que.front();
que.pop();
if (now.v == p2){
qm = now.w;
break;
}
if (vis[now.v]) continue;
vis[now.v] = 1;
for (int i = 0; i < graph[now.v].size(); i++)
if (!vis[graph[now.v][i].v])
que.push(Node(graph[now.v][i].v, now.w+1));
}
while (!que.empty()) que.pop();
vis.assign(n+1, 0);
que.push(Node(p1, 0));
while (!que.empty()){
Node now = que.front();
que.pop();
if (now.v == p2){
bf = now.w;
break;
}
if (vis[now.v]) continue;
vis[now.v] = 1;
for (int i = 0; i < graph[now.v].size(); i++)
if (!vis[graph[now.v][i].v])
que.push(Node(graph[now.v][i].v, now.w+graph[now.v][i].w));
}
cout << qm << " " << bf << endl;
return 0;
}
/*
15 7 2
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14
*/ 
全部评论
(1) 回帖