DFS算法问题求助：任意奶牛出发的最大可达奶牛数计算异常

我看了你的代码，问题确实出在DFS函数的回溯逻辑缺失上。咱们一步步拆解问题：

核心问题分析 #

你的DFS函数里，当访问到奶牛i并递归调用dfs(i)后，完全没有做回溯操作——既没有把全局变量cnt减回去，也没有将cows[i].visited重置为false。这会导致两个致命错误：

1. cnt的值会一直累加，递归返回后无法回到上一层的计数状态，统计的覆盖数完全失真
2. 已访问的奶牛标记没有还原，同一轮DFS（同一个起始点）的后续分支无法正确遍历其他路径

修正后的代码 #

首先是修复后的DFS函数，补上关键的回溯步骤：

#include <iostream>
using namespace std;

int n;
int best = 0;
int cnt = 1;

struct cow {
    int x, y, p;
    bool visited = false;
} cows[201];

bool adj[201][201];

// 优化：用整数运算避免浮点数精度问题，同时防止溢出
bool access(int a, int b) {
    long long dx = cows[b].x - cows[a].x;
    long long dy = cows[b].y - cows[a].y;
    long long dist_sq = dx * dx + dy * dy;
    long long p_sq = (long long)cows[a].p * cows[a].p;
    return dist_sq <= p_sq;
}

void dfs(int cow1) {
    // 先更新当前最优值，当前cnt就是当前路径的覆盖奶牛数
    if (cnt > best) {
        best = cnt;
    }
    for (int i = 1; i <= n; i++) {
        if (!cows[i].visited && adj[cow1][i]) {
            cnt++;
            cows[i].visited = true;
            dfs(i);
            // 回溯：恢复计数和访问状态
            cnt--;
            cows[i].visited = false;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> cows[i].x >> cows[i].y >> cows[i].p;
    }

    // 构建邻接矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                adj[i][j] = access(i, j);
            } else {
                adj[i][j] = false; // 自己到自己不需要通信
            }
        }
    }

    // 遍历每个起始点
    for (int i = 1; i <= n; i++) {
        cnt = 1;
        cows[i].visited = true;
        dfs(i);
        // 重置所有访问状态
        for (int j = 1; j <= n; j++) {
            cows[j].visited = false;
        }
    }

    cout << best << endl;
    return 0;
}

关键修改说明 #

1. 回溯逻辑：在递归调用dfs(i)之后，必须将cnt减1、cows[i].visited设回false，这样回到上一层递归时，状态才是正确的，能继续遍历其他分支。
2. 距离计算优化：把pow替换成整数乘法，避免浮点数精度误差，同时用long long防止整数溢出（当坐标差值较大时，平方后很容易超出int的范围）。
3. 最优值更新时机：把cnt > best的判断放在DFS函数开头，确保每进入一个节点就更新一次最优值，不会漏掉当前路径的计数。

内容的提问来源于stack exchange，提问作者Bob Wang