std::time()计时异常致图着色代码提前终止问题求助

核心问题 #

• 提前终止异常：针对3节点完全图、初始颜色为RGB的测试用例，当时间限制设置为≤3秒时，代码未耗尽设定时长就直接输出"Impossible"，但该用例实际存在合法解（例如节点1→G、节点2→B、节点3→R）。
• 时间计算异常：输出end - start得到结果6，与预期的时间差不符。

问题根源 #

1. 时间检测逻辑漏洞 #

• 全局变量end仅在TryPaint循环内和主循环开头更新，主循环的终止条件end - start < tl在TryPaint执行期间不会实时刷新，导致单次TryPaint快速失败时，主循环可能直接退出，未达到时间限制。
• std::time()返回秒级时间戳，精度不足，且主循环仅在每次TryPaint前更新时间，无法及时检测超时。

2. 着色策略的致命缺陷 #

当前代码固定选择可选颜色的第一个元素，完全没有随机性：

• 若随机洗牌后节点顺序为1→2→3，节点1初始为R，只能选G/B；假设选G后，节点2初始为G，相邻节点1已着色G，可选颜色只剩R，但R是初始颜色被排除，直接导致失败。
• 每次TryPaint都会因固定选择逻辑快速失败，主循环几次后可能因end更新不及时，误判为超时。

3. 时间变量初始化与全局污染 #

主函数中连续执行std::time(&start);和std::time(&end);，理论时间差应为0，但全局变量end易被意外修改，导致时间计算出现异常值。

修复方案 #

1. 替换高精度计时方式 #

用std::chrono替代std::time()，实现毫秒级精度的超时检测，避免秒级误差。

2. 修复着色选择的随机性 #

在可选颜色中随机选择，同时用std::shuffle（替代已弃用的random_shuffle）打乱节点处理顺序，确保每次尝试的多样性。

3. 实时更新超时检测 #

在TryPaint内部的每个节点处理步骤前，以及主循环的每次迭代前，都实时检测时间，避免提前终止。

4. 消除全局变量污染 #

改用局部变量封装计时逻辑，避免全局变量被意外修改。

修复后的完整代码 #

#include <chrono>
#include <iostream>
#include <vector>
#include <set>
#include <random>
#include <algorithm>

// 高精度时钟，毫秒级计时
using Clock = std::chrono::high_resolution_clock;
const int TIME_LIMIT_MS = 3000; // 3秒时间限制

void excludeColor(std::vector<bool>& available, const char& color) {
    if (color == 'R') {
        available[0] = false;
    } else if (color == 'G') {
        available[1] = false;
    } else {
        available[2] = false;
    }
}

std::string getAvailableColors(const std::vector<bool>& available) {
    std::string choices;
    if (available[0]) choices += 'R';
    if (available[1]) choices += 'G';
    if (available[2]) choices += 'B';
    return choices;
}

bool tryPaint(const std::vector<std::set<int>>& edges, std::string& paint, int nodeCount, const Clock::time_point& startTime) {
    std::vector<bool> painted(nodeCount + 1, false);
    std::vector<int> nodes;
    for (int i = 1; i <= nodeCount; ++i) {
        nodes.push_back(i);
    }
    // 用标准随机引擎打乱节点顺序
    static std::mt19937 rng(std::random_device{}());
    std::shuffle(nodes.begin(), nodes.end(), rng);

    std::string tempPaint = paint;
    for (int node : nodes) {
        // 实时检测超时
        auto now = Clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(now - startTime).count();
        if (elapsed >= TIME_LIMIT_MS) {
            return false;
        }

        std::vector<bool> available = {true, true, true};
        // 排除节点初始颜色
        excludeColor(available, paint[node]);
        // 排除相邻已着色节点的颜色
        for (int neighbor : edges[node]) {
            if (painted[neighbor]) {
                excludeColor(available, tempPaint[neighbor]);
            }
        }

        std::string choices = getAvailableColors(available);
        if (choices.empty()) {
            return false;
        }
        // 随机选择颜色
        std::uniform_int_distribution<int> dist(0, choices.size() - 1);
        char selectedColor = choices[dist(rng)];
        tempPaint[node] = selectedColor;
        painted[node] = true;
    }
    paint = tempPaint;
    return true;
}

int main() {
    auto startTime = Clock::now();
    int nodeCount, edgeCount;
    std::cin >> nodeCount >> edgeCount;
    std::string paint;
    std::cin >> paint;
    paint = "#" + paint; // 节点索引从1开始
    std::vector<std::set<int>> edges(nodeCount + 1);
    for (int i = 0; i < edgeCount; ++i) {
        int a, b;
        std::cin >> a >> b;
        edges[a].insert(b);
        edges[b].insert(a);
    }

    bool success = false;
    while (!success) {
        auto now = Clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(now - startTime).count();
        if (elapsed >= TIME_LIMIT_MS) {
            break;
        }
        success = tryPaint(edges, paint, nodeCount, startTime);
    }

    if (success) {
        std::cout << paint.substr(1) << std::endl;
    } else {
        std::cout << "Impossible" << std::endl;
    }

    // 调试用：输出实际耗时
    auto endTime = Clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count();
    std::cout << "实际耗时: " << elapsed << "ms" << std::endl;
    return 0;
}

关键修改说明 #

• 计时系统：改用std::chrono::high_resolution_clock，实现毫秒级精度的超时检测，避免全局变量污染。
• 随机性优化：用std::mt19937随机引擎打乱节点顺序，在可选颜色中随机选择，大幅提高找到合法解的概率。
• 超时检测：在每个节点处理前都实时检测时间，确保不会提前终止。
• 代码规范：重命名函数提高可读性，替换已弃用的random_shuffle为标准的std::shuffle。

测试验证 #

针对提供的测试用例：

3 3
RGB
1 2
2 3
1 3

修复后的代码会在3秒内找到合法解（如GBR或BRG），不会提前输出"Impossible"，时间计算也会准确显示实际耗时。

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