怪怪程序求调
  • 板块学术版
  • 楼主White_AL
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/10/19 18:27
  • 上次更新2023/11/2 12:47:02
查看原帖
怪怪程序求调
376083
White_AL楼主2023/10/19 18:27

求助,仅在dev-cpp环境下编译后返回值异常

主函数发现没有运行就返回异常值了

#include <bits/stdc++.h>
//using namespace std;

struct node {
	int v, dis;
};
std::vector<node> tr[310];
int mmat[310][310];
//bool flag[310];
int trdis[310][310];
int n, s;
int fa[310][10];
int depth[310];
int maxdis[310];
void gen_tree(int x, int dep) {
	depth[x] = dep;
	for (int i = 1; i <= 9; i++) {
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
	}
	for (int i = 0; i < tr[x].size(); i++) {
		node u = tr[x][i];
		if (fa[u.v][0] == 0) {
			//printf("%d's father is %d\n", u.v, x);
			fa[u.v][0] = x;
			gen_tree(u.v, dep + 1);
		}
	}
}
int lca(int x, int y) {
	if (x == y) {
		return x;
	} 
	if (depth[x] < depth[y]) {
		std::swap(x, y); 
	}
	int tmp = 9;
	while (depth[x] > depth[y]) {
		if (depth[fa[x][tmp]] < depth[y]) {
			tmp--;
			continue;
		}
		x = fa[x][tmp];
		tmp--;
	}
	if (x == y) {
		return x;
	}
	tmp = 9;
	while (fa[x][0] != fa[y][0]) {
		if (fa[x][tmp] == fa[y][tmp]) {
			tmp--;
			continue;
		}
		x = fa[x][tmp];
		y = fa[y][tmp];
		tmp--;
		
		
	}
	return fa[x][0];
}


int main() {
	//cout << "ok" << endl;
	std::cin >> n >> s; 
	for (int i = 1; i < n; i++) {
		int u, v, w;
		std::cin >> u >> v >> w;
		tr[u].push_back({v, w});
		tr[v].push_back({u, w});
		mmat[u][v] = w;
		mmat[v][u] = w;
	}
	fa[1][0] = 1;
	gen_tree(1, 1);
	int maxroute = -1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int t = lca(i, j);
			//printf("%d ", t);
			int ssum = 0;
			int l;
			l = i;
			while (l != t) {
				ssum += mmat[l][fa[l][0]];
				l = fa[l][0];
			}
			l = j;
			while (l != t) {
				ssum += mmat[l][fa[l][0]];
				l = fa[l][0];
			}
			trdis[i][j] = ssum;
			maxdis[i] = std::max(ssum, maxdis[i]);
			//printf("%d ", sum);
			maxroute = std::max(maxroute, ssum);
		}
		//putchar('\n');
	}
	int ans = 3000000;
	std::pair<int, int> r[900100];
	int rcnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			if (maxroute == trdis[i][j]) {
				rcnt++;
				r[rcnt] = {i, j};
			}
		}
	}
	for (int i = 1; i <= rcnt; i++) {
		int route[310] = { 0 };
		int roulen;
		int t = lca(r[i].first, r[i].second);
		roulen = depth[t] * 2 - depth[r[i].first] - depth[r[i].second];
		int tmp = r[i].first;
		for (int j = 1; j <= depth[t] - depth[r[i].first]; j++) {
			route[j] = tmp;
			tmp = fa[tmp][0];
		}
		route[depth[t] - depth[r[i].first] + 1] = t;
		tmp = r[i].second;
		for (int j = roulen; j >= roulen - (depth[t] - depth[r[i].second]) + 1; j--) {
			route[j] = tmp;
			tmp = fa[tmp][0];
		}
		for (int j = 1; j <= roulen; j++) {
			printf("%d ", route[j]);
		}
		putchar('\n');
	}
	return 0;
}```
2023/10/19 18:27
加载中...