第4和第7RE了,开大了空间也没用,不知道哪里出问题了,求大佬帮帮本蒟蒻
查看原帖
第4和第7RE了,开大了空间也没用,不知道哪里出问题了,求大佬帮帮本蒟蒻
798945
zsn1434楼主2022/10/31 21:31
#include<iostream>
#include<string.h>
#include<cstdio>
#include<queue>
#define max1 105
using namespace std;
int n;
vector<int> rem[max1];
vector<int>rem2[max1];
queue<int>b;
int depth = 0;
int dp[max1];
int dp2[max1];
int dp3[max1];
int dp4[max1];
int size1=0, size2 = 0;
void bfs(int k) {
	b.push(k);
	depth++;
	dp[k] = 1;
	while (!b.empty()) {
		int fr = b.front(); 
		for (int i = 0; i < rem[fr].size(); i++) {
			int right = rem[fr][i];
			b.push(right);
			dp[right] = dp[fr] + 1;//从父节点继承深度加1
			depth = max(dp[right], depth);
		}
		b.pop();
	}
}
void dfs(int k,int *dp,int& size) {//为了找到两个目标的公共父节点,记录它们的节点值。
	dp[++size] = k;
	int nex = rem2[k][0];
	while (!rem2[nex].empty()) {
		dp[++size] = nex;
		nex = rem2[nex][0];
	}
	dp[++size] = nex;
}
int main()
{
	cin >> n;
	int left, right;
	for (int i = 1; i < n; i++) {
		scanf("%d %d", &left,&right);
		rem[left].push_back(right);
		rem2[right].push_back(left);//用来反过来找父节点
	}
	cin >> left >> right;
	bfs(1);
	dfs(left,dp3,size1);
	dfs(right, dp4, size2);
	int If = 0;
	int sum = 0;
	for (int i = 1; i <= size1; i++) {
		for (int j = 1; j <= size2; j++) {
			if (dp3[i] == dp4[j]) {
				If = 1;
				sum += (i - 1) * 2 + j - 1;//找到了第一个公共父节点后,就可以确认两点间的最短距离了.
			}
		}
		if (If)
			break;
	}
	int t_max = 0;
	for (int i = 1; i < n; i++) {
		dp2[dp[i]]++;//用于寻找相同深度的结点数量.
		t_max = max(dp2[dp[i]], t_max);
	}
	cout << depth << endl << t_max<<endl<<sum;
	return 0;
}
2022/10/31 21:31
加载中...