50分代码求调
  • 板块P1395 会议
  • 楼主清溪墨染
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/2 22:25
  • 上次更新2024/12/3 15:51:45
查看原帖
50分代码求调
354666
清溪墨染楼主2024/12/2 22:25

大佬们求助,为什么这段代码只能做对一半,我感觉逻辑没问题啊

#include<iostream>   
#include<vector>   
using namespace std;
   
int n;  // 节点数量   
vector<vector<int>> map;  // 邻接表   
vector<int> subTree;  // 子树节点数量   
vector<bool> visited;  // 访问标记数组   
vector<int> dp;  // 动态规划数组   
int minDistanceSum;  // 最小距离和   
int targetNode;  // 目标节点
   
// 计算子树大小的DFS函数   
void countSubTree(int node) {
    visited[node] = true;
    for (int i : map[node]) {
        if (!visited[i]) {
            countSubTree(i);
            subTree[node] += subTree[i];
        }
    }   
}
   
// 计算从根节点到所有节点距离和的DFS函数   
void countDistances(int node, int distance) {
    visited[node] = true;
    dp[1] += distance;
    for (int i : map[node]) {
        if (!visited[i]) {
            countDistances(i, distance + 1);
        }
    }   
}
   
// 计算每个节点的距离和并更新最小距离和的节点   
void solve(int node) {
    visited[node] = true;
    for (int i : map[node]) {
        if (!visited[i]) {
            dp[i] = dp[node] + n - 2 * subTree[i];
            if (dp[i] < minDistanceSum) {
                targetNode = i;
                minDistanceSum = dp[i];
            }
            solve(i);  // 递归调用solve
        }
    }   
}
   
int main() {
    cin >> n;
    map.resize(n + 1);
    subTree.resize(n + 1, 1);
    visited.resize(n + 1, false);
    dp.resize(n + 1);

    // 读取输入,构建树的邻接表
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        map[a].push_back(b);
        map[b].push_back(a);
    }

    // 计算子树大小
    countSubTree(1);

    // 重置访问标记数组
    fill(visited.begin(), visited.end(), false);

    // 计算从根节点到所有节点的距离和
    countDistances(1, 0);

    // 初始化最小距离和和目标节点
    minDistanceSum = dp[1];
    targetNode = 1;

    // 重置访问标记数组
    fill(visited.begin(), visited.end(), false);

    // 计算每个节点的距离和并更新最小距离和的节点
    solve(1);

    // 输出目标节点和最小距离和
    cout << targetNode << " " << minDistanceSum;

    return 0;   
}

2024/12/2 22:25
加载中...