华为嵌入式软件比赛2024

仓库链接：https://github.com/maxswordsman/HWEmbeddedSoftwareAlgorithm2024

一、项目总结

名称：

2024 第五届华为嵌入式软件挑战比赛

比赛描述：

通过C++编程，构建具有N个节点M条边的光网络（无向连通图），网络中的每条边代表一条光纤，每条光纤上存在相同数量的光通道。网络上运行着多条光业务，每条业务有起点、终点、通道宽度和价值。路径上的每条边使用连续的通道编号，业务之间不能共享相同通道。比赛场景中会有多个独立的测试场景，每个场景可能会发生多次光纤中断。程序需设计一种算法，对因光纤中断受影响的业务进行重新规划。确保在多次光纤故障后，网络中存在尽可能多的未死亡业务，最大化业务总价值

主要工作：

赛题要求初始化以及故障处理，从标准输入读取网络结构和初始业务数据，并构建相应的图和业务对象，并对每一个测试场景读取发生的故障边的编号，进行故障处理

业务重规划，对于受影响的业务，尝试使用广度优先搜索（BFS）和深度优先搜索（DFS）算法进行路径重规划，首先尝试BFS重新规划受影响的业务路径。若BFS未能成功，则进一步尝试DFS进行二次规划。这种混合使用两种算法的方法提高了业务重新规划的成功率

资源的释放，对于成功重规划的业务，释放其原有的资源；对于未能成功重规划的业务，保持其原有资源占用状态不变

整体优化，首先对BFS算法进行优化，使其可以解决无法遍历重边的情况；其次优化通道选择，在BFS算法重新规划业务路径时，优先选择连续空间最小的通道，以提高资源利用率；再者增加反向搜索，当正向的BFS搜索未能找到合适的路径时，尝试反向搜索以增加找到可行路径的机会；最后价高者先动，优先处理价值更高的业务

二、valid.CPP相关语法

1.变长参数

// 定义了一个名为 overload4 的宏，用于选择合适的 rep 或 per 宏。这个宏接受多个参数，并返回第5个参数 e，用于选择正确的宏
# define overload4(a, b, c, d, e, ...) e
// 定义了一个名为 rep 的宏，用于根据参数的个数选择合适的 rep 宏
# define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
// 定义了一个名为 per 的宏，用于根据参数的个数选择合适的 per 宏
# define per(...) overload4(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__)

（1）part1

1	#define overload4(a, b, c, d, e, ...) e

该部分定义的宏，实现参数重载。它使用了C预处理器的变长参数（variadic arguments）功能：

a, b, c, d, e 是固定参数，共5个

... 是变长参数，表示可以接受任意数量的附加参数

在这个宏的实现中，只返回第5个参数 e。不论传入的参数是什么，宏展开时都会只返回第5个参数 e，如：

overload4(1, 2, 3, 4, 5, 6, 7) 会展开成 5

overload4(x, y, z, w, v) 会展开成 v

（2）part2

1	# define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

这个宏利用了 overload4 宏来实现参数重载。它的步骤如下：

__VA_ARGS__ 是预处理器的一个特殊标识符，表示传递给宏的所有参数

overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)将所有传递给 rep 的参数 __VA_ARGS__以及 rep4, rep3, rep2, rep1 一起传递给 overload4

根据传递给 rep 的参数个数，overload4 会选择合适的 rep 宏：

如果有4个或更多参数，则选择 rep4

如果有3个参数，则选择 rep3

如果有2个参数，则选择 rep2

如果只有1个参数，则选择 rep1

最后，使用 __VA_ARGS__ 再次传递参数，从而调用具体的 rep 宏

结合part1部分进行分析，如下：

若调用rep宏
1
rep(i, 1, 10)
这会展开为
1
overload4(i, 1, 10, rep4, rep3, rep2, rep1)(i, 1, 10)
然后 overload4 宏会选择第五个参数（part1提到的返回第五个参数），即 rep3，所以展开为
1
rep3(i, 1, 10)
而 rep3 宏定义为：
1
#define rep3(i, a, b) for (int i = a; i < (b); ++i)
最终展开为：
1
for (int i = 1; i < 10; ++i)

（3）part3

1	#define per(...) overload4(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__)

这个宏的作用与 rep 类似，只不过它是用于倒序循环。它的步骤如下：

__VA_ARGS__ 是传递给宏的所有参数

overload4(__VA_ARGS__, per4, per3, per2, per1) 将所有传递给 per 的参数 __VA_ARGS__ 以及 per4, per3, per2, per1 一起传递给 overload4

根据传递给 per 的参数个数，overload4 会选择合适的 per 宏：

如果有4个或更多参数，则选择 per4

如果有3个参数，则选择 per3

如果有2个参数，则选择 per2

如果只有1个参数，则选择 per1

最后，使用 __VA_ARGS__ 再次传递参数，从而调用具体的 per 宏

2.遍历给定集合子集

1	#define for_subset(t, s) for (int t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))

宏的定义：

参数解释：

t：循环变量，用于遍历子集

s：集合，宏会遍历 s 的所有子集

重点：

1	(t - 1) & (s)：

这里的目的是生成下一个子集

t - 1 减少 t 的值，去掉 t 的最低位的 1

& (s) 用位与运算符保留 t - 1 中在 s 中出现的位

通过这种方式，t 会遍历 s 的所有子集

例如：

初始状态：t = 5（即 0b101）

第一次迭代：

条件：t >= 0，成立

更新：t = (t - 1) & s = 4 & 5 = 4（即 0b100）

第二次迭代：

条件：t >= 0，成立

更新：t = (t - 1) & s = 3 & 5 = 1（即 0b001）

第三次迭代：

条件：t >= 0，成立

更新：t = (t - 1) & s = 0 & 5 = 0（即 0b000）

第四次迭代：

条件：t >= 0，成立

更新：t = (t == 0 ? -1 : (t - 1) & s) = -1

循环结束：t < 0，循环条件不成立

通过上述步骤，t 的取值分别是 5（0b101），4（0b100），1（0b001），0（0b000），这就是 5 的所有子集

二进制中子集定义：

二进制表示 101 表示在三位二进制数中，第一位和第三位是 1，第二位是 0。我们可以生成的所有子集如下

保留所有位：101（即 5）

只保留第一位：100（即 4）

只保留第三位：001（即 1）

不保留任何位：000（即 0）

这些组合就是 101 所有的子集。换句话说，5 的所有子集可以看作是 5 的二进制表示中每个 1 位的所有可能组合

3.使用宏简化常用的STL操作

# define all(x) x.begin(), x.end()
# define len(x) int(x.size())
# define elif else if
# define eb emplace_back
# define mp make_pair
# define mt make_tuple
# define fi first
# define se second
# define stoi stoll

1	#define all(x) x.begin(), x.end()

all(x) 宏将容器 x 的起始迭代器和结束迭代器展开，通常用于标准库算法中

如：

1 2	std::vector<int> vec = {4, 3, 2, 1}; std::sort(all(vec)); // 相当于 std::sort(vec.begin(), vec.end());

1	# define eb emplace_back

eb 是 emplace_back 的简写形式，用于在容器末尾高效地插入一个元素

1	#define mp make_pair

mp 是 make_pair 的简写形式，用于创建一个 std::pair 对象

1	#define mt make_tuple

mt 是 make_tuple 的简写形式，用于创建一个 std::tuple 对象

如：

1	std::tuple<int, double, std::string> t = mt(1, 2.5, "example"); // 相当于 std::make_tuple(1, 2.5, "example");

三、baseLine

该版本是我们实现的基础算法：

可以实现对受影响业务的重新规划，但是该算法中的BFS无法遍历重边情况

对受影响业务进行价值排序，优先处理价值较大的业务

1.变量以及类声明

// 记录一个测试用例下，每一个测试场景的规划成功业务数量/规划失败业务数量
class TestCaseInfo
{
public:
    TestCaseInfo():successCnt(0),failedCnt(0){}
    int TCCnt;
    int successCnt;
    int failedCnt;
};
vector<TestCaseInfo> TestCase;

// 节点类
class Node {
public:
    int id;  // 节点编号
    int channel_change_capacity;  // 变通道次数--初始化之后就不会变化
    int usedChannelCnt;           // 该节点变通道次数被使用计数

    // 构造函数
    Node(int id = 0, int capacity = 0) : id(id), channel_change_capacity(capacity) ,usedChannelCnt(ZERO){}
};

// 光纤类
class Edge{
public:
    // 边的编号 冗余
    int edgeId;
    int from;
    int to;
    vector<bool> channels;  // 通道占用情况，true 表示被占用，false 表示可用
    bool is_faulty; // 边是否故障
    unordered_set<int> passServices; // 经过该边的业务ID

    int freeContinuousChannelsMaxNum;   // 空闲的连续编号最大通道宽度
    vector<pair<int,int>> freeContinuousChannelsRange;  // 空闲的连续编号通道区间

    // 构造函数
    Edge(int from = 0, int to = 0) :
            from(from), to(to),edgeId(CurCntEdgeId),is_faulty(false),freeContinuousChannelsMaxNum(InitChannelNums)
    {
        channels.resize(InitChannelNums+1, false);  // 初始化41个通道，下标0不使用
    }
};

// 业务类
class Service {
public:
    int id;
    int start;
    int end;
    int width; // 业务通道宽度
    int edge_nums;   // 经过边的数量
    vector<int> path;  // 业务路径上的边编号
    vector<pair<int, int>> channels;  // 每条边上的通道区间
    int value;  // 业务价值
    vector<int> changeChannelNodes;  // 记录当前业务在那些节点变换通道了
    bool isDie;


    // 构造函数
    Service(int id=0,int start = 0, int end = 0, int width = 0, int value = 0):
            id(id),start(start),end(end),width(width),value(value),edge_nums(ZERO),isDie(false){}
};

// 图类
class Graph {
public:
    vector<Node> nodes;
    vector<Edge> edges;
    map<int, vector<int>> adjacency_list;

    map<int, Service> services;

    // 初始状态备份
    vector<Node> initial_nodes;
    vector<Edge> initial_edges;
    map<int, Service> initial_services;

    // 构造函数，预置空对象确保从1开始编号
    Graph();
    // 为图增加节点
    void addNode(int id, int capacity);
    // 为图增加边
    void addEdge(int from, int to);
    // 为图增加服务
    void addService(int id,int start, int end, int width, int value);
    // 初始化图
    void initialize();
    // 重置图状态到初始输入状态
    void resetGraphState();
    // 输出重新规划的业务详情
    void displayReplanServicesInfo(vector<int> &rePlanned_servicesId);

    // 标记故障边
    void markFaultyEdge(int edgeFailedId);
    // 检查通道是否可用
    bool isChannelAvailable(const Edge& edge, int channel_start, int channel_end);
    // 更新通道占用情况
    void updateChannelOccupation(Edge& edge, int channel_start, int channel_end, bool occupy);

    // 找到两个容器中相同的元素，并且返回
    vector<int> findCommonElements(const vector<int>& vec1, const vector<int>& vec2);
    // 找到两个容器中相同的元素的对应的索引
    pair<int, int> findCommonElementIndices(const vector<int>& vec1, const vector<int>& vec2, int commonElement);
    // 去除pair1,中pair1与pair2交集的部分
    pair<int, int> removeOverlap(const pair<int, int>& pair1, const pair<int, int>& pair2);
    // 将vec1中存在的vec2的元素全部去除
    void removeElements(vector<int>& vec1, const vector<int>& vec2);

    // 业务路径重新规划前，释放老路径的通道资源，以至于新路径规划时可以使用
    void bfsPlanBeforeHandOldPath(Service &service);
    // 释放业务老路径上剩余的资源
    void freeOldPathResources(map<int, Service>& oldServices);
    // 业务重新规划失败，还原业务老路径的资源占用，将规划失败的业务标记为死亡
    void restoreOldPathResources(Service &service);

    // 使用BFS重新规划路径
    bool bfsRePlanService(Service& service,map<int, Service>& oldServices);

    // 计算每一个测试场景开始时，业务总价值(对于同一个测试用例，每一个测试场景开始时，业务总价值相同，因为当一个测试场景结束后，光网络会恢复至初始状态)
    int getBeginValue();
    // 计算每一个测试场景结束后，光网络上存活的业务总价值
    int getEndValue();
    // 计算该测试场景下的得分
    int getScore(int beginValue, int endValue);
    // 计算测试用例总得分
    int getCaseSumScore(vector<int> &vec);
};

2.构造光网络

该部分通过图类的基础成员函数，构造光网络，该部分的内容：

构造网络

为图，添加节点，添加边

添加边上的业务

当接收单个场景的故障边时，对其进行标记

当场景结束时，对光网络进行复原，等待下一个场景测试

接收输入数据，对光网络进行初始化

对重新规划成功的业务信息进行输出

// 构造函数，预置空对象确保从1开始编号
Graph::Graph()
{
    nodes.emplace_back(); // 添加一个空的节点对象
    edges.emplace_back(); // 添加一个空的边对象
}

// 增加节点
void Graph::addNode(int id, int capacity)
{
    nodes.emplace_back(id, capacity);
}

// 增加边
void Graph::addEdge(int from, int to)
{
    edges.emplace_back(from, to);
    // 邻接表
    adjacency_list[from].push_back(CurCntEdgeId);
    adjacency_list[to].push_back(CurCntEdgeId);
}

//增加服务
void Graph::addService(int id,int start, int end, int width, int value)
{
    services[id] = Service(id,start,end,width,value);
}

// 初始化图
void Graph::initialize()
{
    cin >> N >> M;  // 节点数和边数
    for (int i = 1; i <= N; i++)
    {
        cin >> Pi;
        addNode(i, Pi);
    }
    for (int i = 1; i <= M; i++)
    {
        cin >> ui >> vi;
        CurCntEdgeId++;
        addEdge(ui, vi);
    }
    // 业务数量
    cin >> J;
    for (int i = 1; i <= J; i++)
    {
        // 业务起点 终点 经边数 通道范围[L,R]--初始不存在变通道 业务价值
        cin >> Src >> Snk >> S >> L >> R >> V;
        int id = i;
        int width = ((R-L) + 1);
        addService(id, Src, Snk, width, V);
        Service& service = services[id];
        // 初始化业务经边数
        service.edge_nums = S;
        // 业务路径 初始化
        for (int j = 1; j <= S; j++)
        {
            int edge_id;
            cin >> edge_id;
            // 当前业务添加路径
            service.path.push_back(edge_id);
            // 当前路径中经过边，所占用的通道对
            service.channels.push_back(make_pair(L,R));
            // 记录经过edge_id边的业务  edges[edge_id].passServices.insert(id);
            edges[edge_id].passServices.insert(id);

            // 当前边被占用的通道进行标记
            for(int j = L;j<=R;j++)
            {
                edges[edge_id].channels[j] = true;
            }
            // 边edge_id最大连续通道宽度,更新
            edges[edge_id].freeContinuousChannelsMaxNum -= width;
        }
    }

    // 备份初始状态
    initial_nodes = nodes;
    initial_edges = edges;
    initial_services = services;
}

// 重置图状态到初始输入状态
void Graph::resetGraphState()
{
    nodes = initial_nodes;
    edges = initial_edges;
    services = initial_services;
    adjacency_list.clear();
    for (int i = 1; i <edges.size(); ++i)
    {
        int from = edges[i].from;
        int to = edges[i].to;
        adjacency_list[from].push_back(i);
        adjacency_list[to].push_back(i);
    }
}

// 输出重新规划的业务详情
void Graph::displayReplanServicesInfo(vector<int> &rePlanned_servicesId)
{
    cout << rePlanned_servicesId.size() << endl;
    for (const int& serviceId : rePlanned_servicesId)
    {
        cout << services[serviceId].id << " " << services[serviceId].path.size() << endl;
        for (size_t i = 0; i < services[serviceId].path.size(); ++i)
        {
            cout << services[serviceId].path[i] << " " << services[serviceId].channels[i].first << " " << services[serviceId].channels[i].second << " ";
        }
        cout << endl;
    }
}

3.通道检查与更新

该部分内容：

当业务重新规划时，需要对业务经过的边上的通道范围是否可用进行判断

边上的连续通道需要满足，业务通道宽度的需求

当业务占用某条边，或者释放某条边，需要对边上连续范围的通道进行占用/释放

当接收到故障边，需要将该边进行标记

// 标记故障边
void Graph::markFaultyEdge(int edgeFailedId)
{
    edges[edgeFailedId].is_faulty = true;
}

// 检查通道是否可用
bool Graph::isChannelAvailable(const Edge& edge, int channel_start, int channel_end)
{
    for (int i = channel_start; i <= channel_end; ++i)
    {
        if (edge.channels[i])
        {
            return false;
        }
    }
    return true;
}

// 更新通道占用情况
void Graph::updateChannelOccupation(Edge& edge, int channel_start, int channel_end, bool occupy)
{
    for (int i = channel_start; i <= channel_end; ++i)
    {
        edge.channels[i] = occupy;
    }
}

4.资源的释放与还原

该部分主要介绍：

在对某个受到影响的业务进行BFS重新规划路径时，释放老路径的通道资源，以至于新路径规划时可以使用路路径的相关资源（除了故障光纤）

在因为某边断纤而受到影响的一批次业务全部处理完毕之后，需要将成功进行重新规划的业务老路径上的资源进行释放，但是规划失败的业务，无法进行资源释放

某业务进行重新规划后，规划失败，需要对该业务老路径上的资源进行，重新占用，并且将该业务标记为死亡，在此次测试用例中，该业务所占用的资源无法进行释放

// 业务路径重新规划前，释放老路径的通道资源，以至于新路径规划时可以使用
void Graph::bfsPlanBeforeHandOldPath(Service &service)
{
    for (int i = 0; i < service.path.size(); ++i)
    {
        updateChannelOccupation(edges[service.path[i]], service.channels[i].first, service.channels[i].second, false); // 释放该边占用的通道资源
        edges[service.path[i]].passServices.erase(service.id);  // 该边经过的业务也需要去除
    }
    // 释放老路径的节点使用的变通道情况
    for(int i = 0;i<service.changeChannelNodes.size();i++)
    {
        --nodes[service.changeChannelNodes[i]].usedChannelCnt;
    }
}

// 释放业务老路径上剩余的资源--该批次受影响业务全部处理后
void Graph::freeOldPathResources(map<int, Service>& oldServices)
{
    for(auto &[key,oService]:oldServices)
    {
        for (int i = 0; i < oService.path.size(); ++i)
        {
            updateChannelOccupation(edges[oService.path[i]], oService.channels[i].first, oService.channels[i].second, false);
        }
        // 释放老路径的节点使用的变通道情况
        for(int i = 0;i<oService.changeChannelNodes.size();i++)
        {
            --nodes[oService.changeChannelNodes[i]].usedChannelCnt;
        }
    }
}

// 业务重新规划失败，还原业务老路径的资源占用，将规划失败的业务标记为死亡
void Graph::restoreOldPathResources(Service &service)
{
    // 还原-释放老路径通道占用情况
    for (int i = 0; i < service.path.size(); ++i)
    {
        updateChannelOccupation(edges[service.path[i]], service.channels[i].first, service.channels[i].second, true);
        // 这条业务死了，不需要将其绑定到路径上
        // edges[service.path[i]].passServices.insert(service.id);  // 该边经过的业务需要添加
    }
    // 还原-释放老路径的节点使用的变通道情况
    for(int i = 0;i<service.changeChannelNodes.size();i++)
    {
        ++nodes[service.changeChannelNodes[i]].usedChannelCnt;
    }
    service.isDie = true;  // 业务作死亡标记
}

5.辅助函数以及其他

该部分主要用于在 BFS 算法为受影响业务规划处新路径时，比对新老路径的不同，占用老路径上新路径上没有使用的资源，等待该测试场景结束之后，统一释放

以及计算得分的相关方法

vector<int> Graph::findCommonElements(const vector<int>& vec1, const vector<int>& vec2)
{
    // 使用unordered_set存储vec1的元素以便快速查找
    unordered_set<int> elementsSet(vec1.begin(), vec1.end());
    vector<int> commonElements;

    // 遍历vec2，查找相同元素
    for (const auto& elem : vec2) {
        if (elementsSet.find(elem) != elementsSet.end()) {
            commonElements.push_back(elem);
            elementsSet.erase(elem);  // 防止重复元素被多次添加
        }
    }

    return commonElements;
}

// 找到两个容器中相同的元素的对应的索引
pair<int, int> Graph::findCommonElementIndices(const vector<int>& vec1, const vector<int>& vec2, int commonElement)
{
    std::pair<int, int> indices(-1, -1);
    // 查找元素在vec1中的索引
    auto it1 = std::find(vec1.begin(), vec1.end(), commonElement);
    if (it1 != vec1.end()) {
        indices.first = std::distance(vec1.begin(), it1);
    }

    // 查找元素在vec2中的索引
    auto it2 = std::find(vec2.begin(), vec2.end(), commonElement);
    if (it2 != vec2.end()) {
        indices.second = std::distance(vec2.begin(), it2);
    }
    return indices;
}

// 去除pair1,中pair1与pair2交集的部分
pair<int, int> Graph::removeOverlap(const pair<int, int>& pair1, const pair<int, int>& pair2) {
    pair<int, int> result(-1,-1);

    // pair1 和 pair2 完全不重叠
    if (pair1.second < pair2.first || pair1.first > pair2.second) {
        result = pair1;
    }
        // pair1 被 pair2 完全覆盖
    else if (pair1.first >= pair2.first && pair1.second <= pair2.second) {
        // 不需要添加任何元素到 result，因为 pair1 完全被覆盖
    }
        // pair1 和 pair2 部分重叠
    else {
        if (pair1.first < pair2.first) {
            result = make_pair(pair1.first, pair2.first-1);
        }
        if (pair1.second > pair2.second) {
            result = make_pair(pair2.second+1, pair1.second);
        }
    }

    return result;
}

// 将vec1中存在的vec2的元素全部去除
void Graph::removeElements(vector<int>& vec1, const vector<int>& vec2) {
    for (int elem : vec2) {
        // 查找并删除vec1中的elem
        vec1.erase(std::remove(vec1.begin(), vec1.end(), elem), vec1.end());
    }
}

// 计算每一个测试场景开始时，业务总价值(对于同一个测试用例，每一个测试场景开始时，业务总价值相同，因为当一个测试场景结束后，光网络会恢复至初始状态)
int Graph::getBeginValue()
{
    set<int> serversIDs;
    // 遍历所有边
    for(int i = 1; i < edges.size(); i++)
    {
        for(int serId : edges[i].passServices)
        {
            // 判断该业务是否是活的
            if(services[serId].isDie == false)
            {
                serversIDs.insert(serId);
            }
        }
    }

    int valueSum = 0;
    // 遍历此时光网络上存活的业务ID
    for(int Id : serversIDs)
    {
        valueSum += services[Id].value;
    }
    return valueSum;
}

// 计算每一个测试场景结束后，光网络上存活的业务总价值
int Graph::getEndValue()
{
    set<int> serversIDs;
    // 遍历所有边
    for(int i = 1; i < edges.size(); i++)
    {
        for(int serId : edges[i].passServices)
        {
            // 判断该业务是否是活的
            if(services[serId].isDie == false)
            {
                serversIDs.insert(serId);
            }
        }
    }

    int valueSum = 0;
    // 遍历此时光网络上存活的业务ID
    for(int Id : serversIDs)
    {
        valueSum += services[Id].value;
    }
    return valueSum;
}

// 计算该测试场景下的得分
int Graph::getScore(int beginValue, int endValue)
{
    int score = 0;
    score = (endValue * 10000) / beginValue;
    return score;
}

// 计算测试用例总得分
int Graph::getCaseSumScore(vector<int> &vec)
{
    int caseSumScore = 0;
    for(int score: vec)
    {
        caseSumScore += score;
    }
    return caseSumScore;
}

/*********************************************其他函数*******************************************/
// 显示初始化输入的业务情况
void displayInitInput(Graph &graph,ofstream &logFile,int &count)
{
    logFile << "--------------初始输入信息情况: "<< count << "---------------" << endl;
    logFile << "-----------------------------" << endl;
    logFile << "业务数量: " << J << endl;
    for(int i = 1;i<=J;i++)
    {
        logFile << "业务编号: "<< graph.services[i].id << " : " << graph.services[i].start << " "
                << graph.services[i].end << " " << graph.services[i].edge_nums << endl;
        for(int j = 0;j<graph.services[i].edge_nums;j++)
        {
            logFile << "边的编号: " <<graph.services[i].path[j] << " : " << "[" << graph.services[i].channels[j].first <<" , " << graph.services[i].channels[j].second << "]" << endl;
        }
        logFile << "当前业务变通道节点: ";
        if(graph.services[i].changeChannelNodes.size() == 0)
        {
            logFile << "无"<< endl;
        }
        else
        {
            for(int k = 0;k<graph.services[i].changeChannelNodes.size();k++)
            {
                logFile << graph.services[i].changeChannelNodes[k] << " ";
            }
            logFile <<endl;
        }
        logFile << "--------" << endl;
    }

    logFile << "-----------------------------" << endl;
    logFile << "边上的业务情况: " << endl;
    for(int i = 1;i<=CurCntEdgeId;i++)
    {
        // 该边上存在业务
        if(graph.edges[i].passServices.size() != 0)
        {
            logFile << "边的编号: " << i << " 边上业务数量: " << graph.edges[i].passServices.size() << endl;
            logFile << "该边的业务情况: " << endl;
            for(auto &e : graph.edges[i].passServices)
            {
                logFile << e << " ";
            }
            logFile << endl;
            logFile << "该边剩余的连续通道最大宽度: " << graph.edges[i].freeContinuousChannelsMaxNum << endl;
            logFile << "--------" << endl;
        }
    }
    logFile << "-----------------------------" << endl;
    logFile << "图的初始信息: " << endl;
    logFile << "邻接表尺寸: " << graph.adjacency_list.size() << "x" << graph.adjacency_list.size() <<endl;
    logFile << "连接信息: " <<endl;
    logFile << "--------" << endl;
    for(int i = 1;i<=graph.adjacency_list.size();i++)
    {
        logFile << "节点 " << i << " : ";
        for(int j = 0;j<graph.adjacency_list[i].size();j++)
        {
            logFile << graph.adjacency_list[i][j] << " ";
        }
        logFile << endl;
    }
    logFile << "--------" << endl;

    logFile << "-----------------------------" << endl;
    logFile << "节点的信息情况: " <<endl;
    for(int i = 1;i<=N;i++)
    {
        logFile << "节点编号: " <<  i << endl;
        logFile << "初始变通道数: " << graph.nodes[i].channel_change_capacity << endl;
        logFile << "该节点的变通道使用次数: " << graph.nodes[i].usedChannelCnt <<endl;
        logFile << "--------" << endl;
    }

    logFile << "-----------------------------" << endl;
    logFile << "边上的空闲通道情况: " << endl;
    for(int i = 1;i<=CurCntEdgeId;i++)
    {
        logFile << "边 "<< i << " 空闲通道: ";
        int start = -1;
        for (int j = 1; j < graph.edges[i].channels.size(); ++j)
        {
            if (graph.edges[i].channels[j] == false)
            {
                if (start == -1) {
                    start = j; // 开始遇到1，记录起始索引
                }
            }
            else if (start != -1)
            {
                // 遇到非1，输出从start到i-1的连续1区间
                logFile << "(" << start << ", " << j - 1 << ")" << " ";
                start = -1; // 重置起始索引
            }
        }
        if (start != -1)
        {
            // 处理数组结尾为1的情况
            logFile << "(" << start << ", " << graph.edges[i].channels.size() - 1 << ")" << " ";
        }
        logFile << endl;
    }
    logFile << endl;
}

// 显示处理某个业务之后资源更新情况(变通道节点/边的通道)
void displayAfterHandlingServiceInput(Graph &graph,ofstream &logFile,int &count)
{
    logFile << "-->节点的信息情况: " <<endl;
    for(int i = 1;i<=N;i++)
    {
        logFile << "---->节点编号: " <<  i << endl;
        logFile << "------>初始变通道数: " << graph.nodes[i].channel_change_capacity << endl;
        logFile << "------>该节点的变通道使用次数: " << graph.nodes[i].usedChannelCnt <<endl;
    }

    logFile << "-->边上的空闲通道情况: " << endl;
    for(int i = 1;i<=CurCntEdgeId;i++)
    {
        logFile << "---->边 "<< i << " 空闲通道: ";
        int start = -1;
        for (int j = 1; j < graph.edges[i].channels.size(); ++j)
        {
            if (graph.edges[i].channels[j] == false)
            {
                if (start == -1) {
                    start = j; // 开始遇到1，记录起始索引
                }
            }
            else if (start != -1)
            {
                // 遇到非1，输出从start到i-1的连续1区间
                logFile << "(" << start << ", " << j - 1 << ")" << " ";
                start = -1; // 重置起始索引
            }
        }
        if (start != -1)
        {
            // 处理数组结尾为1的情况
            logFile << "(" << start << ", " << graph.edges[i].channels.size() - 1 << ")" << " ";
        }
        logFile << endl;
    }
    logFile << "-->边上的经由的业务情况: " << endl;
    for(int i = 1;i<=CurCntEdgeId;i++)
    {
        logFile << "---->边 "<< i << " 经由业务: ";
        for (auto &elem: graph.edges[i].passServices)
        {
            logFile << elem << " ";
        }
        logFile << endl;
    }
    logFile << endl;
}

stringstream getTime()
{
    // 获取当前时间点
    auto now = std::chrono::system_clock::now();

    // 转换为时间戳
    std::time_t now_c = std::chrono::system_clock::to_time_t(now);

    // 转换为tm结构
    std::tm now_tm = *std::localtime(&now_c);

    // 创建一个字符串流
    std::stringstream ss;

    // 设置时间格式
    ss << std::put_time(&now_tm, "%Y-%m-%d %H:%M:%S");

    return ss;
}

/*********************************************其他函数*******************************************/

6.BFS重规划方法

（1）BFS核心思路

视频教程：跳转

BFS（宽搜）的过程是从根部开始，向下逐层扩展

BFS是通过队列实现，使用queue创建队列，BFS的过程，通过队列来维护序列的状态空间，入队就排队等待，出队就扩展子节点们入队

adjust[x]用于存储x节点的邻居节点（邻接表），visit[x]标记x是否以及被访问过，是否以及入过队列q。队列q用于存储入队的点的序列

实例：

邻接表：

/*
 * 1-->2,3
 * 2-->1,4,5,6
 * 3->1,7,8
 * .....
 */
int N = 8;
vector<int> adjust[N+1] = {{},{2,3},{1,4,5,3},{1,7,8},{2},{2},{2},{3},{3}};

Code：

int N = 8;
vector<int> adjust[N+1]; // 邻接表--节点从1开始
vector<int> visit(N+1, -1);;  // 标记节点是否被访问
queue<int> q;  

void bfs()
{
    visit[1] = 1;
    q.push(1);
    while(q.size()){
        int x = q.front();
        q.pop();
        // printf("%d 出队\n", x);
        for(int y : adjust[x]){
            if(vis[y]) 
                // 该节点被访问过
                continue;
            vis[y] = 1;
            // printf("%d 入队\n", y);
            q.push(y);
        }
    }
}

出入队列 q 情况

1出队

2入队

3入队

2出队

4入队

5入队

6入队

3出队

7入队

8入队

4出队

5出队

6出队

7出队

8出队

由此可以印证：入队就排队等待，出队就扩展子节点们入队

此外，通过出入队列q的情况，可知，BFS 队列中元素层次满足两段性即，队列中只可能同时存在2层（以内或2层）的节点

（2）对图使用BFS获得BFS树

如上图：

节点1入队，并出队
    其子节点 4 2 6 入队
大儿子4节点出队
    节点4子节点 3 5 入队
节点2出队
    节点2子节点 1 5 已经访问过，不入队
节点6出队
    节点6子节点 1 4 已经访问过，不入队
节点3出队
    节点3子节点 4 已经访问过，不入队
节点5出队
    节点5子节点 4 已经访问过，不入队

通过图构建了图下方的BFS 树

（3）项目中BFS整体流程

该部分是用于对受到影响的业务进行资源重新规划的方法，其整体流程如下：

释放业务老路径资源：

业务重新规划时，可使用该业务其老路径上的资源，但是故障边上的资源无法使用

释放老路径上通道占用情况

释放老路径上节点使用的变通道情况

BFS搜素最短路径：

规划失败

还原业务老路径的资源占用，将该业务标记为死亡

规划成功

通过记录的BFS算法寻路时记录的状态，获取新路径

对比新路径资源的不同

将重新规划后老路径中新路径没有使用的通道资源进行重新占用（需要等到该批次受到影响的业务处理完毕，才能释放）

将重新规划后老路径中新路径没有使用的节点变通道次数进行占用

将重新规划的业务新路径资源进行占用

更新当前重新规划成功的业务的当前资源情况

规划核心：

queue<int> q作为队列，节点入队就排队等待，出队就扩展子节点们入队

使用vector<int> parent(nodes.size(), -1)，记录路径上的父节点。具体来说，parent[node] 表示在到达节点 node 时，从哪个父节点过来的。同时也是用于记录搜索路径时候，那个节点已经访问了

使用vector<int> parent_edge(nodes.size(), -1)，记录路径上的边编号，具体来说，用于记录到达索引index节点，是经过parent_edge[index]边

使用vector<int> used_channels(nodes.size(), -1)，记录使用的通道编号，具体来说，用于记录在到达每个节点时所使用的通道编号区间的起点

节点出队

遍历与其连接的边

若为故障边，跳过

若边的邻居节点已经访问过，则继续跳过

得到出队节点，来源边的通道起点start，用于判断该连接边是否有满足业务的连续通道[start,start+width-1]

若出队节点为业务起点，则可以随意选择通道起点，只要满足业务通道宽度需求

若出队节点非业务起点，同时连接边也无满足连续通道 [start,start+width-1]，则判断该节点是否有变通道能力，若有，则遍历连接边上的空闲通道，是否有连续空闲通道范围满足width

// 使用BFS重新规划路径
bool Graph::bfsRePlanService(Service& service,map<int, Service>& oldServices)
{
    queue<int> q;
    vector<int> parent(nodes.size(), -1); // 记录路径上的父节点  记录路径上的父节点。具体来说，parent[node] 表示在到达节点 node 时，从哪个父节点过来的
    vector<int> parent_edge(nodes.size(), -1); // 记录路径上的边编号
    vector<int> used_channels(nodes.size(), -1); // 记录使用的通道编号  用于记录在到达每个节点时所使用的通道编号区间的起点
    q.push(service.start);
    parent[service.start] = service.start;
    used_channels[service.start] = service.channels[0].first; // 初始通道编号

    // 业务重新规划前，释放老路径的通道占用资源
    // 原因：对受影响业务进行重新规划时，它可以使用该业务老路径的相关资源（故障边上的资源无法使用）
    bfsPlanBeforeHandOldPath(service);

    while (!q.empty())
    {
        int node = q.front();
        q.pop();

        if (node == service.end) break; // 到达终点

        for (int edge_id : adjacency_list[node])
        {
            Edge& edge = edges[edge_id];
            if (edge.is_faulty) continue; // 跳过故障边

            int neighbor = (edge.from == node) ? edge.to : (edge.to == node) ? edge.from : -1;
            if (neighbor == -1 || parent[neighbor] != -1) continue; // 跳过已访问节点

            int current_channel = used_channels[node];

            // 判断该边的连续空闲范围 是否满足业务宽度需求
            if (isChannelAvailable(edge, current_channel, current_channel + service.width - 1))
            {
                q.push(neighbor);
                parent[neighbor] = node;
                parent_edge[neighbor] = edge_id;
                used_channels[neighbor] = current_channel; // 继续使用当前通道
            }
            else
            {
                if(node == service.start)
                {
                    for (int ch = 1; ch <= 40 - service.width + 1; ++ch)
                    {
                        if (isChannelAvailable(edge, ch, ch + service.width - 1))
                        {
                            q.push(neighbor);
                            parent[neighbor] = node;
                            parent_edge[neighbor] = edge_id;
                            used_channels[neighbor] = ch; // 使用新的通道
                            break;
                        }
                    }
                }
                else
                {
                    if ((nodes[node].channel_change_capacity - nodes[node].usedChannelCnt) > 0)
                    {
                        // 使用当前节点处的变通道次数
                        for (int ch = 1; ch <= 40 - service.width + 1; ++ch)
                        {
                            if (isChannelAvailable(edge, ch, ch + service.width - 1))
                            {
                                q.push(neighbor);
                                parent[neighbor] = node;
                                parent_edge[neighbor] = edge_id;
                                used_channels[neighbor] = ch; // 使用新的通道
                                break;
                            }
                        }
                    }
                }
            }
        }
    }

    // 规划失败
    if (parent[service.end] == -1)  // 无法到达目标
    {
        // 业务重新规划失败，标记为死亡，死亡的业务占用的通道资源以及变节点次数均不会释放，之后也不会对其进行重新规划
        // 还原-在BFS算法开始之前对业务老路径释放的通道资源情况
        // 并且对该规划失败的业务标记死亡
        restoreOldPathResources(service);
        return false;
    }

    // 业务路径重新规划成功，获取新路径的资源情况
    vector<int> new_path;
    vector<pair<int, int>> new_channels;
    vector<int> newChangeChannelNodes;
    vector<int> newPathNodes;
    for (int v = service.end; v != service.start; v = parent[v])
    {
        new_path.push_back(parent_edge[v]);
        newPathNodes.push_back(v);
        new_channels.push_back(make_pair(used_channels[v], used_channels[v] + service.width - 1));
    }
    newPathNodes.push_back(service.start);
    reverse(new_path.begin(), new_path.end());
    reverse(new_channels.begin(), new_channels.end());
    reverse(newPathNodes.begin(),newPathNodes.end());

    // 比对该业务新老路径资源
    // 1.先判断是否使用了相同的边上的，共有的通道资源，若新路径使用了老路径的部分通道资源，老路径需要进行剔除
    // repeatedEdges 存储了相同边的编号
    vector<int> repeatedEdges;
    repeatedEdges = findCommonElements(new_path,service.path);
    for(int i = 0;i<repeatedEdges.size();i++)
    {
        int commonElement = repeatedEdges[i];
        // 获得老路径 与 新路径 共有边分别在各自 path中的索引值
        pair<int, int> indices = findCommonElementIndices(service.path,new_path,commonElement);
        // commonElement --> new_path in indices.first
        // commonElement --> service.path in indices.second
        if (indices.first != -1 && indices.second != -1)
        {
            pair<int,int> result = removeOverlap(service.channels[indices.first],new_channels[indices.second]);
            // 完全不重叠 or 部分重叠
            if(result.first != -1 && result.second != -1)
            {
                // result 即 该业务老路径上 这条边上的 剩余资源
                service.channels[indices.first] = result;
            }
            else
            {
                // 完全覆盖---这条共有边上老路径所使用的通道资源，被新路径完全使用
                // 将这条边，在老路径中剔除
                service.path.erase(service.path.begin() + indices.first);
                service.channels.erase(service.channels.begin() + indices.first);
            }
        }
    }

    // 2.判断是否对相同的节点使用了变通道次数
    // 同时新路径上使用了变通道能力的节点，次数进行更新
    for(int i = 0;i<new_channels.size()-1;i++)
    {
        if(new_channels[i] != new_channels[i+1])
        {
            ++nodes[newPathNodes[i+1]].usedChannelCnt;
            newChangeChannelNodes.push_back(newPathNodes[i+1]);
        }
    }
    // 判断新老路径上是否对同一个节点使用了变通道的次数
    // 若新路径使用了老路径changeChannelNodes中的节点的变通道次数，老路径changeChannelNodes中需要将其剔除
    vector<int> repeatedChangeChannelNodes;
    repeatedChangeChannelNodes = findCommonElements(newChangeChannelNodes,service.changeChannelNodes);
    // 将service.changeChannelNodes 中 被新路径使用的变通道节点能力的节点去除
    if(repeatedChangeChannelNodes.size() != 0)
    {
        removeElements(service.changeChannelNodes,repeatedChangeChannelNodes);
    }

    // 将该业务老路径剩余的资源进行占用
    oldServices[service.id] = Service(service.id,service.start,service.end,service.width,service.value);
    oldServices[service.id].path = service.path;
    oldServices[service.id].channels = service.channels;
    oldServices[service.id].changeChannelNodes = service.changeChannelNodes;
    oldServices[service.id].edge_nums = service.path.size();
    // 将老路径剩余资源占用
    for (int i = 0; i < oldServices[service.id].path.size(); ++i)
    {
        updateChannelOccupation(edges[oldServices[service.id].path[i]], oldServices[service.id].channels[i].first,
                                oldServices[service.id].channels[i].second, true); // 占用的通道资源
    }
    // 将老路径的剩余节点使用的变通道情况进行占用
    for(int i = 0;i<oldServices[service.id].changeChannelNodes.size();i++)
    {
        ++nodes[oldServices[service.id].changeChannelNodes[i]].usedChannelCnt;
    }

    // 对重新规划的新路径通道进行占用
    for (int i = 0; i < new_path.size(); ++i)
    {
        updateChannelOccupation(edges[new_path[i]], new_channels[i].first, new_channels[i].second, true);
        edges[new_path[i]].passServices.insert(service.id);
    }


    service.path = new_path;
    service.channels = new_channels;
    // 更新路径上那些节点使用了变通道
    service.changeChannelNodes = newChangeChannelNodes;

    // 更新业务的经边数量
    service.edge_nums = new_path.size();

    return true;
}

7.主函数

在主函数中对受影响的业务按照价值排序，优先处理价值高的业务

int main()
{
    Graph graph;
    graph.initialize();

    // 处理故障和业务重规划
    int T;
    cin >> T;
    while (T--)
    {
        while (cin >> edgeFailed && edgeFailed != -1)
        {
            // 标记业务故障边
            graph.markFaultyEdge(edgeFailed);
            // 分析受影响的业务编号
            unordered_set<int> affected_services_set = graph.edges[edgeFailed].passServices;
            // 业务按照价值进行降序排序---------------------------
            vector<int> affected_services(affected_services_set.begin(),affected_services_set.end());
            sort(affected_services.begin(), affected_services.end(), [&graph](int a, int b) {
                return graph.services[a].value > graph.services[b].value;  // 更改比较逻辑以实现降序
            });

            // 实现业务重规划逻辑
            vector<int> rePlanned_servicesId; // 记录重新规划成功的业务id
            map<int, Service> oldServices;  // 存储业务老路径占用的资源
            for (int service_id : affected_services)
            {
                Service& service = graph.services[service_id];

                // 业务重新规划成功
                if(graph.bfsRePlanService(service,oldServices))
                {
                    // 将规划成功的业务id 记录至 rePlanned_servicesId中
                    rePlanned_servicesId.push_back(service_id);
                }
            }
            // 输出重新规划的业务详情
            graph.displayReplanServicesInfo(rePlanned_servicesId);
            // 对老路径剩余的资源进行释放
            graph.freeOldPathResources(oldServices);

        }
        // 重置图状态以处理下一个场景
        graph.resetGraphState();
    }

    return 0;
}

四、AdvanceV1

该版本在baseLine的基础上：

增加DFS算法，当BFS算法无法找到重边时，使用DFS业务进行二次规划

对baseLine中的BFS算法进行优化，增加重边处理机制，使得其可以遍历重边，找到业务合适的路径

1.DFS重规划算法

（1）DFS算法核心思路

视频教程：跳转

DFS 深搜的过程是，从根进入，向下走，走到底，向上走，最后从根部退出

DFS 的实现：

深搜是通过系统栈实现

递归调用的过程，系统是通过栈去维护函数的状态空间。系统栈记录函数返回地址、局部变量、参数传递等

向下走，压栈；向上走，出栈

实例：

如下图，8节点、7边的图

代码实现如下：

#include <iostream>
#include <vector>

using namespace std;

const int N = 8;
vector<int> e[N+1];

/*
 * @param: parent是父节点，用于去重 
 */
void dfs(int u, int parent)
{
    for(auto v: e[u])
    {   
        // 节点已经访问过
        if(v==parent) continue;
        // 递归访问u的邻接节点v，其父亲节点为u
        dfs(v,u);
    }
}

int main()
{
    int n,m;
    // 输入图的节点数 边数
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        // 输入边的连接信息
        cin >> a >>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    // 开始递归从树的根节点开始
    dfs(1,0);
    return 0;
}

递归调用的过程：

DFS递归顺序如下图，从根节点开始，从上往下，将左边的分支全部访问过后再访问右边的分支，也是自上而下

1 5 2 入栈

2 无子节点，则出栈，则 6 3 入栈

3 无子节点，则出栈，则 8 入栈

8 无子节点，则出栈，则 6 无其他子节点，出栈，则 7 入栈

7 无子节点，则出栈，则 5 无其他子节点，出栈，则 4 入栈

4 无子节点，则出栈，则 1 无其他子节点，出栈

根节点入，根节点出

（2）对图使用DFS获得DFS树

入下图，所示，左边为图，右边为DFS树

该图的邻接表如下：

根结点 1 入栈

1 的邻接的节点 4 入栈，4 邻接的节点 3 入栈，3邻接的节点 4（已经访问过，跳过），则其另一个邻接的节点 5 入栈， 5 邻接的节点 3 4 均访问过则跳过

5 出栈， 3 出栈，4 的邻接节点 6 入栈

6 的邻接节点 1 4 均访问过则跳过，则 6出栈

4 的邻接节点 3 5 1 6 均访问过，已经无其他节点，则出栈

1 的邻接节点 2 入栈

代码实现：

#include <iostream>
#include <vector>

using namespace std;

const int N = 6;
vector<int> e[N+1];
int n,m,a,b;
// 用于判断节点是否已经访问过
int vis[N+1](N+1,-1);


void dfs(int u)
{
    vis[u] = true;
    for(auto v: e[u])
    {
        // 节点已经访问过
        if(vis[v]) continue;
        // 递归访问u的邻接节点v
        dfs(v);
    }
}

int main()
{
    // 输入图的节点数 边数
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        // 输入边的连接信息
        cin >> a >>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    // 开始递归从树的根节点开始
    dfs(1);
    return 0;
}

（3）项目中使用 DFS 整体流程

该部分是用于对受到影响的业务进行资源重新规划的方法，其整体流程如下：

释放业务老路径资源：

业务重新规划时，可使用该业务其老路径上的资源，但是故障边上的资源无法使用

释放老路径上通道占用情况

释放老路径上节点使用的变通道情况

BFS搜素最短路径：

规划失败

还原业务老路径的资源占用，将该业务标记为死亡

规划成功

通过 DFS 算法寻路时，使用vector<int>模拟栈，记录的路径上的节点pathNode，pathEdge,used_channels得到业务重新规划得到的新路径

对比新路径资源的不同

将重新规划后老路径中新路径没有使用的通道资源进行重新占用（需要等到该批次受到影响的业务处理完毕，才能释放）

将重新规划后老路径中新路径没有使用的节点变通道次数进行占用

将重新规划的业务新路径资源进行占用

更新当前重新规划成功的业务的当前资源情况

规划核心：

vector<int> pathNode作为模拟栈，用于记录新规划路径上经过的节点

使用vector<int> pathEdge，用于记录新规划路径上经过的边

使用vector<int> used_channels，用于记录新规划路径上经过边上使用的通道起始点

使用vector<bool> vis(nodes.size(), false)，用于记录节点是否已经访问过

递归DFS

在dfsRePlanService内部调用dfs()函数进行业务路径冲规划，dfs()核心是递归DFS，从起点开始，走到底，若在这个过程中没有遇到终点，则进行回溯（各个模拟栈，需要出栈），到达上一个存在分支的节点，将该节点的另外一个分支同样走到底

当遇到业务终点，则成功返回

当递归DFS的系统栈中已经无元素（dfs()函数，参数等），则会return false

头文件：

class Graph 
{
public:
	.....
     // 使用DFS重新规划路径
	bool dfsRePlanService(Service& service,map<int, Service>& oldServices);
    
private:
    .....
	// 递归DFS（dfsRePlanService方法内部调用）
    bool dfs(int node, Service &service, vector<bool> &vis, vector<int> &pathNode, vector<int> &pathEdge, vector<int> &used_channels);
        
}

源文件：

// 使用DFS重新规划路径
bool Graph::dfsRePlanService(Service& service,map<int, Service>& oldServices)
{
    vector<bool> vis(nodes.size(), false);
    vector<int> pathNode;
    vector<int> pathEdge;
    vector<int> used_channels;
    used_channels.push_back(service.channels[0].first);

    // 业务重新规划前，释放老路径的通道占用资源
    // 原因：对受影响业务进行重新规划时，它可以使用该业务老路径的相关资源（故障边上的资源无法使用）
    bfsPlanBeforeHandOldPath(service);

    /****************规划失败****************/
    if(!dfs(service.start, service, vis, pathNode,pathEdge, used_channels))
    {
        // 业务重新规划失败，标记为死亡，死亡的业务占用的通道资源以及变节点次数均不会释放，之后也不会对其进行重新规划
        // 还原-在BFS算法开始之前对业务老路径释放的通道资源情况
        // 并且对该规划失败的业务标记死亡
        restoreOldPathResources(service);
        return false;
    }
    /****************规划失败****************/

    /****************规划成功****************/
    // 根据 pathNode pathEdge used_Channels得到新路径
    vector<pair<int, int>> new_channels;
    vector<int> newChangeChannelNodes;
    // 获取路径上的通道范围
    for(int i = 1; i < used_channels.size(); i++)
    {
        // used_channels 会将业务原来路径 起点通道也添加进入，因此从1开始
        new_channels.push_back(make_pair(used_channels[i], used_channels[i] + service.width - 1));
    }

    // 比对该业务新老路径资源
    // 1.先判断是否使用了相同的边上的，共有的资源通道
    // repeatedEdges 存储了相同边的编号
    vector<int> repeatedEdges;
    repeatedEdges = findCommonElements(pathEdge,service.path);
    for(int i = 0;i<repeatedEdges.size();i++)
    {
        int commonElement = repeatedEdges[i];
        // 获得老路径 与 新路径 共有边分别在各自 path中的索引值
        pair<int, int> indices = findCommonElementIndices(service.path,pathEdge,commonElement);
        // commonElement --> new_path in indices.first
        // commonElement --> service.path in indices.second
        if (indices.first != -1 && indices.second != -1)
        {
            pair<int,int> result = removeOverlap(service.channels[indices.first],new_channels[indices.second]);
            // 完全不重叠 or 部分重叠
            if(result.first != -1 && result.second != -1)
            {
                // result 即 该业务老路径上 这条边上的 剩余资源
                service.channels[indices.first] = result;
            }
            else
            {
                // 完全覆盖---这条共有边上老路径所使用的通道资源，被新路径完全使用
                // 将这条边，在老路径中剔除
                service.path.erase(service.path.begin() + indices.first);
                service.channels.erase(service.channels.begin() + indices.first);
            }
        }
    }
    // 2.判断是否对相同的节点使用了变通道次数
    // 同时新路径上使用了变通道能力的节点，次数进行更新
    for(int i = 0;i<new_channels.size()-1;i++)
    {
        if(new_channels[i] != new_channels[i+1])
        {
            ++nodes[pathNode[i+1]].usedChannelCnt;
            newChangeChannelNodes.push_back(pathNode[i+1]);
        }
    }

    // 判断新老路径上是否对同一个节点使用了变通道的次数
    vector<int> repeatedChangeChannelNodes;
    repeatedChangeChannelNodes = findCommonElements(newChangeChannelNodes,service.changeChannelNodes);
    // 将service.changeChannelNodes 中 被新路径使用的变通道节点能力的节点去除
    if(repeatedChangeChannelNodes.size() != 0)
    {
        removeElements(service.changeChannelNodes,repeatedChangeChannelNodes);
    }
    // 将该业务老路径剩余的资源进行占用
    oldServices[service.id] = Service(service.id,service.start,service.end,service.width,service.value);
    oldServices[service.id].path = service.path;
    oldServices[service.id].channels = service.channels;
    oldServices[service.id].changeChannelNodes = service.changeChannelNodes;
    oldServices[service.id].edge_nums = service.path.size();
    // 将老路径剩余资源占用
    for (int i = 0; i < oldServices[service.id].path.size(); ++i)
    {
        updateChannelOccupation(edges[oldServices[service.id].path[i]], oldServices[service.id].channels[i].first,
                                oldServices[service.id].channels[i].second, true); // 占用的通道资源
    }
    // 释放老路径的节点使用的变通道情况
    for(int i = 0;i<oldServices[service.id].changeChannelNodes.size();i++)
    {
        ++nodes[oldServices[service.id].changeChannelNodes[i]].usedChannelCnt;
    }

    // 对重新规划的新路径通道进行占用
    for (int i = 0; i < pathEdge.size(); ++i)
    {
        updateChannelOccupation(edges[pathEdge[i]], new_channels[i].first, new_channels[i].second, true);
        edges[pathEdge[i]].passServices.insert(service.id);
    }

    service.path = pathEdge;
    service.channels = new_channels;
    // 更新路径上那些节点使用了变通道
    service.changeChannelNodes = newChangeChannelNodes;

    // 更新业务的经边数量
    service.edge_nums = pathEdge.size();

    return true;
    /****************规划成功****************/
}

// 递归DFS
bool Graph::dfs(int node, Service &service, vector<bool> &vis, vector<int> &pathNode,
                vector<int> &pathEdge, vector<int> &used_channels)
{
    vis[node] = true;
    pathNode.push_back(node);

    // 到达终点
    if(node == service.end)
        return true;

    for(int edge_id: adjacency_list[node])
    {
        Edge& edge = edges[edge_id];
        if (edge.is_faulty) continue; // 跳过故障边

        int neighbor = (edge.from == node) ? edge.to : (edge.to == node) ? edge.from : -1;
        if (neighbor == -1 || vis[neighbor] != false) continue; // 跳过已访问节点

        int current_channel = used_channels.back();

        // 判断该边的连续空闲范围 是否满足业务宽度需求
        if (isChannelAvailable(edge, current_channel, current_channel + service.width - 1))
        {
            pathEdge.push_back(edge_id);
            used_channels.push_back(current_channel);
            if(dfs(neighbor, service, vis, pathNode, pathEdge, used_channels))
                return true;
        }
        else
        {
            if(node == service.start)
            {
                for (int ch = 1; ch <= 40 - service.width + 1; ++ch)
                {
                    if (isChannelAvailable(edge, ch, ch + service.width - 1))
                    {
                        pathEdge.push_back(edge_id);
                        used_channels.push_back(ch);
                        if(dfs(neighbor, service, vis, pathNode, pathEdge, used_channels))
                            return true;
                    }
                }
            }
            else
            {
                if ((nodes[node].channel_change_capacity - nodes[node].usedChannelCnt) > 0)
                {
                    // 使用当前节点处的变通道次数
                    for (int ch = 1; ch <= 40 - service.width + 1; ++ch)
                    {
                        if (isChannelAvailable(edge, ch, ch + service.width - 1))
                        {
                            pathEdge.push_back(edge_id);
                            used_channels.push_back(ch);
                            if(dfs(neighbor, service, vis, pathNode, pathEdge, used_channels))
                                return true;
                        }
                    }
                }
            }
        }
    }

    pathNode.pop_back();
    pathEdge.pop_back();
    used_channels.pop_back();
    return false;
}

2.BFS增加处理重边机制

（1）项目中使用处理重边的BFS整体流程

规划核心（相较于基础的BFS重规划算法）：

该算法相较于基础的BFS重规划算法，增加了vector<int> vis_edge(edges.size(),-1)判断某边是否访问过，在for (int edge_id : adjacency_list[node])中只有在neighbor与edge_id均被访问过，才会跳过边edge_id的访问，如此可以有效的遍历重边情况

头文件：

Graph
{
public:
    .....
	// 解决BFS baseLine无法处理重边的问题
    bool bfsRePlanService2(Service& service,map<int, Service>& oldServices);

private:
    .....
    // 判断队列中是否已经出现了元素x（bfsRePlanService2方法内部调用）
    bool isQEleRepeat(queue<int> &q, int &neighbor);
    // 递归DFS（dfsRePlanService方法内部调用）
    bool dfs(int node, Service &service, vector<bool> &vis, vector<int> &pathNode, vector<int> &pathEdge, vector<int> &used_channels);
    // 在可处理重边的BFS算法中，得到相关状态后，使用该方法找合适路径，是对得到的状态进行DFS（bfsRePlanService2方法内部调用）
    bool findPathDfs(int node, Service &service, vector<int> &pathNode, vector<int> &pathEdge, vector<int> &pathChan,
                     vector<vector<int>> &parent, vector<vector<int>> &parentEdge, vector<vector<int>> &usedChan, int channel);
    // （findPathDfs方法内部调用）
    bool findPath(int node, Service &service, vector<int> &pathNode,
                  vector<int> &pathEdge, vector<int> &pathChan,
                  vector<vector<int>> &parent, vector<vector<int>> &parentEdge, vector<vector<int>> &usedChan);
}

源文件：

// 判断队列中是否已经出现了元素x
bool Graph::isQEleRepeat(queue<int> &q, int &neighbor)
{
    queue<int> tempQ = q;
    while (!tempQ.empty())
    {
        if(tempQ.front() == neighbor)
        {
            return true;
        }
        tempQ.pop();
    }
    return false;
}

// 使用BFS重新规划路径---可以处理重边
bool Graph::bfsRePlanService2(Service& service,map<int, Service>& oldServices)
{
    queue<int> q;
    queue<int> qAll;
    vector<vector<int>> parent(nodes.size(), vector<int>(1, -1)); // 记录路径上的父节点  记录路径上的父节点（同时也用于判断某节点是否已经访问过）。具体来说，parent[node] 表示在到达节点 node 时，从哪个父节点过来的
    vector<vector<int>> parent_edge(nodes.size(), vector<int>(1, -1)); // 记录路径上的边编号
    vector<vector<int>> used_channels(nodes.size(), vector<int>(1, -1)); // 记录使用的通道编号  用于记录在到达每个节点时所使用的通道编号区间的起点
    vector<int> vis_edge(edges.size(),-1); // 判断边是否访问

    q.push(service.start);
    qAll.push(service.start);
    parent[service.start][0] = service.start;
    used_channels[service.start][0] = service.channels[0].first; // 初始通道编号

    // 业务重新规划前，释放老路径的通道占用资源
    // 原因：对受影响业务进行重新规划时，它可以使用该业务老路径的相关资源（故障边上的资源无法使用）
    bfsPlanBeforeHandOldPath(service);

    while (!q.empty())
    {
        int node = q.front();
        q.pop();

        if (node == service.end) break; // 到达终点

        for (int edge_id : adjacency_list[node])
        {
            Edge& edge = edges[edge_id];
            if (edge.is_faulty) continue; // 跳过故障边

            int neighbor = (edge.from == node) ? edge.to : (edge.to == node) ? edge.from : -1;
            if ((neighbor == -1 || parent[neighbor][0] != -1) && (vis_edge[edge_id]!=-1)) continue; // 跳过已访问节点与边
            // 若neighbor为node的父节点，也跳过
            if(std::find(parent[node].begin(), parent[node].end(), neighbor) != parent[node].end()) continue;


            vis_edge[edge_id] = edge_id;

            int usedChanSize = used_channels[node].size();
            for(int i=0;i<usedChanSize;i++)
            {
                int current_channel = used_channels[node][i];

                // 判断该边的连续空闲范围 是否满足业务宽度需求
                if (isChannelAvailable(edge, current_channel, current_channel + service.width - 1))
                {
                    if(isQEleRepeat(qAll, neighbor) == false)
                    {
                        qAll.push(neighbor);
                        q.push(neighbor);
                    }

                    if (parent[neighbor].size()==1 && parent[neighbor][0]==-1)
                        parent[neighbor][0] = node;
                    else
                        parent[neighbor].push_back(node);

                    if (parent_edge[neighbor].size()==1 && parent_edge[neighbor][0]==-1)
                        parent_edge[neighbor][0] = edge_id;
                    else
                        parent_edge[neighbor].push_back(edge_id);

                    if (used_channels[neighbor].size()==1 && used_channels[neighbor][0]==-1)
                        used_channels[neighbor][0] = current_channel;
                    else
                        used_channels[neighbor].push_back(current_channel);
                }
                else
                {
                    if(node == service.start)
                    {
                        for (int ch = 1; ch <= 40 - service.width + 1; ++ch)
                        {
                            if (isChannelAvailable(edge, ch, ch + service.width - 1))
                            {
                                if(isQEleRepeat(qAll, neighbor) == false)
                                {
                                    qAll.push(neighbor);
                                    q.push(neighbor);
                                }

                                if (parent[neighbor].size()==1 && parent[neighbor][0]==-1)
                                    parent[neighbor][0] = node;
                                else
                                    parent[neighbor].push_back(node);

                                if (parent_edge[neighbor].size()==1 && parent_edge[neighbor][0]==-1)
                                    parent_edge[neighbor][0] = edge_id;
                                else
                                    parent_edge[neighbor].push_back(edge_id);

                                // 选择新通道
                                if (used_channels[neighbor].size()==1 && used_channels[neighbor][0]==-1)
                                    used_channels[neighbor][0] = ch;
                                else
                                    used_channels[neighbor].push_back(ch);
                                break;
                            }
                        }
                    }
                    else
                    {
                        if ((nodes[node].channel_change_capacity - nodes[node].usedChannelCnt) > 0)
                        {
                            // 使用当前节点处的变通道次数
                            for (int ch = 1; ch <= 40 - service.width + 1; ++ch)
                            {
                                if (isChannelAvailable(edge, ch, ch + service.width - 1))
                                {
                                    if(isQEleRepeat(qAll, neighbor) == false)
                                    {
                                        qAll.push(neighbor);
                                        q.push(neighbor);
                                    }

                                    if (parent[neighbor].size()==1 && parent[neighbor][0]==-1)
                                        parent[neighbor][0] = node;
                                    else
                                        parent[neighbor].push_back(node);

                                    if (parent_edge[neighbor].size()==1 && parent_edge[neighbor][0]==-1)
                                        parent_edge[neighbor][0] = edge_id;
                                    else
                                        parent_edge[neighbor].push_back(edge_id);

                                    // 选择新通道
                                    if (used_channels[neighbor].size()==1 && used_channels[neighbor][0]==-1)
                                        used_channels[neighbor][0] = ch;
                                    else
                                        used_channels[neighbor].push_back(ch);
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // 规划失败
    if (parent[service.end][parent[service.end].size()-1] == -1)  // 无法到达目标
    {
        // 业务重新规划失败，标记为死亡，死亡的业务占用的通道资源以及变节点次数均不会释放，之后也不会对其进行重新规划
        // 还原-在BFS算法开始之前对业务老路径释放的通道资源情况
        // 并且对该规划失败的业务标记死亡
        restoreOldPathResources(service);
        return false;
    }


    // 新路径情况
    vector<int> new_path;
    vector<pair<int, int>> new_channels;
    vector<int> newChangeChannelNodes;
    vector<int> newPathNodes;

    vector<int> pathNodes;
    vector<int> pathEdges;
    vector<int> pathChan;
    // 找到路径了
    if(findPath(service.end, service, pathNodes, pathEdges, pathChan, parent, parent_edge, used_channels))
    {
        new_path = pathEdges;
        newPathNodes = pathNodes;
        reverse(new_path.begin(), new_path.end());
        reverse(newPathNodes.begin(), newPathNodes.end());
        for(int i = pathChan.size()-1; i>=0; i--)
        {
            new_channels.push_back(make_pair(pathChan[i], pathChan[i] + service.width - 1));
        }
    }
    else
    {
        // 没有找到路径
        // 还原-释放老路径通道占用情况
        restoreOldPathResources(service);
        return false;
    }


    // 比对该业务新老路径资源
    // 1.先判断是否使用了相同的边上的，共有的资源通道
    // repeatedEdges 存储了相同边的编号
    vector<int> repeatedEdges;
    repeatedEdges = findCommonElements(new_path,service.path);
    for(int i = 0;i<repeatedEdges.size();i++)
    {
        int commonElement = repeatedEdges[i];
        // 获得老路径 与 新路径 共有边分别在各自 path中的索引值
        pair<int, int> indices = findCommonElementIndices(service.path,new_path,commonElement);
        // commonElement --> new_path in indices.first
        // commonElement --> service.path in indices.second
        if (indices.first != -1 && indices.second != -1)
        {
            pair<int,int> result = removeOverlap(service.channels[indices.first],new_channels[indices.second]);
            // 完全不重叠 or 部分重叠
            if(result.first != -1 && result.second != -1)
            {
                // result 即 该业务老路径上 这条边上的 剩余资源
                service.channels[indices.first] = result;
            }
            else
            {
                // 完全覆盖---这条共有边上老路径所使用的通道资源，被新路径完全使用
                // 将这条边，在老路径中剔除
                service.path.erase(service.path.begin() + indices.first);
                service.channels.erase(service.channels.begin() + indices.first);
            }
        }
    }
    // 2.判断是否对相同的节点使用了变通道次数
    // 同时新路径上使用了变通道能力的节点，次数进行更新
    for(int i = 0;i<new_channels.size()-1;i++)
    {
        if(new_channels[i] != new_channels[i+1])
        {
            ++nodes[newPathNodes[i+1]].usedChannelCnt;
            newChangeChannelNodes.push_back(newPathNodes[i+1]);
        }
    }
    // 判断新老路径上是否对同一个节点使用了变通道的次数
    vector<int> repeatedChangeChannelNodes;
    repeatedChangeChannelNodes = findCommonElements(newChangeChannelNodes,service.changeChannelNodes);
    // 将service.changeChannelNodes 中 被新路径使用的变通道节点能力的节点去除
    if(repeatedChangeChannelNodes.size() != 0)
    {
        removeElements(service.changeChannelNodes,repeatedChangeChannelNodes);
    }
    // 将该业务老路径剩余的资源进行占用
    oldServices[service.id] = Service(service.id,service.start,service.end,service.width,service.value);
    oldServices[service.id].path = service.path;
    oldServices[service.id].channels = service.channels;
    oldServices[service.id].changeChannelNodes = service.changeChannelNodes;
    oldServices[service.id].edge_nums = service.path.size();
    // 将老路径剩余资源占用
    for (int i = 0; i < oldServices[service.id].path.size(); ++i)
    {
        updateChannelOccupation(edges[oldServices[service.id].path[i]], oldServices[service.id].channels[i].first,
                                oldServices[service.id].channels[i].second, true); // 占用的通道资源
    }
    // 占用老路径的剩余节点使用的变通道情况
    for(int i = 0;i<oldServices[service.id].changeChannelNodes.size();i++)
    {
        ++nodes[oldServices[service.id].changeChannelNodes[i]].usedChannelCnt;
    }

    //-------------------------------
    // 对重新规划的新路径通道进行占用
    for (int i = 0; i < new_path.size(); ++i)
    {
        updateChannelOccupation(edges[new_path[i]], new_channels[i].first, new_channels[i].second, true);
        edges[new_path[i]].passServices.insert(service.id);
    }


    service.path = new_path;
    service.channels = new_channels;
    // 更新路径上那些节点使用了变通道
    service.changeChannelNodes = newChangeChannelNodes;
    // 更新经过的节点
    service.pathNodes = newPathNodes;

    // 更新业务的经边数量
    service.edge_nums = new_path.size();


    return true;
}

（2）递归找到合适路径

相较于基础的BFS版本，可处理重边的BFS算法，有如下主要不同点：

vector<vector<int>> parent(nodes.size(), vector<int>(1, -1)) ，这是用于记录到达该节点的所有父节点，因此这是一个二维列表的形式

vector<vector<int>> parent_edge(nodes.size(), vector<int>(1, -1))，这是用于记录到达该节点的所有边，因此这是一个二维列表的形式

vector<vector<int>> used_channels(nodes.size(), vector<int>(1, -1))，这是用于记录到达该节点使用的所有通道范围的左起点，因此这是一个二维列表的形式

例如如下图：

该业务的起点是1，终点是5，业务通道宽度为3

使用方法bfsRePlanService2，得到的parent，parent_edge，used_channels，是如下形式：

1
2
3

vector<vector<int>> parent = {{-1},{1},{1},{2,2},{3,3},{4},{4}};
vector<vector<int>> parent_edge = {{-1},{-1},{1},{2,3},{4,4},{5},{6}};;
vector<vector<int>> used_channels = {{-1},{35},{35},{35,37},{35,37},{37},{37}};;

为了通过这三组数据，找到正确的路径，需要使用DFS，获得解答树，如下图：

如下是使用DFS，对得到的相关状态处理的方法：

bool Graph::findPathDfs(int node, Service &service, vector<int> &pathNode,vector<int> &pathEdge, vector<int> &pathChan,
         vector<vector<int>> &parent, vector<vector<int>> &parentEdge, vector<vector<int>> &usedChan,int channel)
{
    pathNode.push_back(node);
    if(node == service.start)
        return true;

    for(int index = 0; index < parent[node].size(); index++)
    {
        if(node == service.start)
        {
            pathEdge.push_back(parentEdge[node][index]);
            pathChan.push_back(usedChan[node][index]);
            if(findPathDfs(parent[node][index], service, pathNode,pathEdge, pathChan,parent, parentEdge, usedChan,usedChan[node][index]))
            {
                return true;
            }
        }
        else
        {
            if(channel == usedChan[node][index])
            {
                pathEdge.push_back(parentEdge[node][index]);
                pathChan.push_back(usedChan[node][index]);
                if(findPathDfs(parent[node][index], service, pathNode,pathEdge, pathChan,parent, parentEdge, usedChan,usedChan[node][index]))
                {
                    return true;
                }
            }
            else
            {
                if(nodes[node].channel_change_capacity - nodes[node].usedChannelCnt > 0)
                {
                    pathEdge.push_back(parentEdge[node][index]);
                    pathChan.push_back(usedChan[node][index]);
                    if(findPathDfs(parent[node][index], service, pathNode,pathEdge, pathChan,parent, parentEdge, usedChan,usedChan[node][index]))
                    {
                        return true;
                    }
                }
            }
        }
    }

    pathNode.pop_back();
    pathEdge.pop_back();
    pathChan.pop_back();
    return false;
}

bool Graph::findPath(int node, Service &service, vector<int> &pathNode,vector<int> &pathEdge, vector<int> &pathChan,
                   vector<vector<int>> &parent, vector<vector<int>> &parentEdge, vector<vector<int>> &usedChan)
{
    for(int index = 0; index < parent[node].size(); index++)
    {
        if(findPathDfs(node, service, pathNode, pathEdge, pathChan, parent, parentEdge, usedChan, usedChan[node][index]))
        {
            return true;
        }
    }
    return false;
}

对于该图得到的结果如下：

1
2
3

pathNode = {5,4,3,2,1};
pathEdge = {5,4,3,1};
pathChan = {37,37,37,35};

从节点1，至终点5：

可以重新规划的路径经过的节点：1->2->3->4->5

经过的边：e1->e3->e4->e5

每条边上的通道范围：[35,37]->[37,39]->[37,39]->[37,39]

结果正确

3.主函数

int main()
{
    // 将标准输入重定向到文件
    if (freopen(redirectPath2, "r", stdin) == NULL)
    {
        std::cerr << "Error opening redirectPath file" << std::endl;
        exit(1);
    }

    Graph graph;
    graph.initialize();

    // 处理故障和业务重规划
    int T;
    cin >> T;
    while (T--)
    {
        while (cin >> edgeFailed && edgeFailed != -1)
        {
            // 标记业务故障边
            graph.markFaultyEdge(edgeFailed);

            // 分析受影响的业务编号
            unordered_set<int> affected_services_set = graph.edges[edgeFailed].passServices;
            // 业务按照价值进行降序排序---------------------------
            vector<int> affected_services(affected_services_set.begin(),affected_services_set.end());
            sort(affected_services.begin(), affected_services.end(), [&graph](int a, int b) {
                return graph.services[a].value > graph.services[b].value;  // 更改比较逻辑以实现降序
            });

            // 实现业务重规划逻辑
            vector<int> rePlanned_servicesId; // 记录重新规划成功的业务id
            map<int, Service> oldServices;  // 存储业务老路径占用的资源
            for (int service_id : affected_services)
            {
                Service& service = graph.services[service_id];

                // 使用BFS2对业务重新规划成功
                if(graph.bfsRePlanService2(service,oldServices))
                {
                    // 将规划成功的业务id 记录至 rePlanned_servicesId中
                    rePlanned_servicesId.push_back(service_id);
                }
                else
                {
                    // 对BFS2规划失败的业务，使用DFS对业务进行二次规划
                    if(graph.dfsRePlanService(service,oldServices))
                    {
                        // 二次规划成功业务复活
                        service.isDie = false;
                        rePlanned_servicesId.push_back(service_id);
                    }
                }
            }

            // 输出重新规划的业务信息
            graph.displayReplanServicesInfo(rePlanned_servicesId);

            // 对老路径剩余的资源进行释放
            graph.freeOldPathResources(oldServices);

        }
        // 重置图状态以处理下一个场景
        graph.resetGraphState();
    }

    return 0;
}

五、AdvanceV2

该版本在AdvanceV1的基础上，对bfsRePlanService2进行优化得到bfsRePlanService3，其中有：

在通道选择时，优先选择满足当前业务通道宽度，但是在该边所有合适的通道范围中为最小的通道，如当前业务宽度为3，在边e1上的通道合适的范围有[1,5]、[10,12]、[20,28]、[35,39]，但是会选择其中范围宽度最小通道，即[10,12]中的[10,12]作为业务通道，如此就会占用连续空闲宽度大的业务通道，这样其他业务宽度大的业务就有更多规划成功的机会（优化通道选择：优先选择连续空间最小的通道，提高资源利用率）

当第一次使用 BFS 算法没有为业务成功规划，则会从业务的终点，向起点去搜索路径，这样由于通道选择等因素的影响，也会使得结果有不同。但是需要注意的是，在进行这一步的优化时，会将业务的终点起点互换，当二次使用 BFS 算法之后，不论成功与否，都需要将业务的起点终点还原（增加反向搜索：当正向的BFS搜索未能找到合适的路径时，尝试反向搜索以增加找到可行路径的机会）

1.相关优化

头文件：

Graph
{
public:
    .....
    // 在bfs2的基础上，通道选择优化，以及初次失败，尝试首尾节点互换，再次搜索
    bool bfsRePlanService3(Service& service,map<int, Service>& oldServices);
    
private:
    .....
    // 寻找最小范围的插入通道(返回通道范围的左边界索引，为-1则没有)
    int findShortestRangeChannel(const vector<bool> &vec, int width);
}

源文件：

// 使用BFS3进行以业务重新规划（对BFS2进行优化）
bool Graph::bfsRePlanService3(Service& service,map<int, Service>& oldServices)
{
    queue<int> q;
    queue<int> qAll;
    vector<vector<int>> parent(nodes.size(), vector<int>(1, -1)); // 记录路径上的父节点  记录路径上的父节点（同时也用于判断某节点是否已经访问过）。具体来说，parent[node] 表示在到达节点 node 时，从哪个父节点过来的
    vector<vector<int>> parent_edge(nodes.size(), vector<int>(1, -1)); // 记录路径上的边编号
    vector<vector<int>> used_channels(nodes.size(), vector<int>(1, -1)); // 记录使用的通道编号  用于记录在到达每个节点时所使用的通道编号区间的起点
    vector<int> vis_edge(edges.size(),-1); // 判断边是否访问


    q.push(service.start);
    qAll.push(service.start);
    parent[service.start][0] = service.start;
    used_channels[service.start][0] = service.channels[0].first; // 初始通道编号

    // 业务重新规划前，释放老路径的通道占用资源
    // 原因：对受影响业务进行重新规划时，它可以使用该业务老路径的相关资源（故障边上的资源无法使用）
    bfsPlanBeforeHandOldPath(service);

    while (!q.empty())
    {
        int node = q.front();
        q.pop();

        if (node == service.end) break; // 到达终点

        for (int edge_id : adjacency_list[node])
        {
            Edge& edge = edges[edge_id];
            if (edge.is_faulty) continue; // 跳过故障边

            int neighbor = (edge.from == node) ? edge.to : (edge.to == node) ? edge.from : -1;
            if ((neighbor == -1 || parent[neighbor][0] != -1) && (vis_edge[edge_id]!=-1)) continue; // 跳过已访问节点与边
            // 若neighbor为node的父节点，也跳过
            if(std::find(parent[node].begin(), parent[node].end(), neighbor) != parent[node].end()) continue;


            vis_edge[edge_id] = edge_id;

            int usedChanSize = used_channels[node].size();
            for(int i=0;i<usedChanSize;i++)
            {
                int current_channel = used_channels[node][i];

                // 判断该边的连续空闲范围 是否满足业务宽度需求
                if (isChannelAvailable(edge, current_channel, current_channel + service.width - 1))
                {
                    if(isQEleRepeat(qAll, neighbor) == false)
                    {
                        qAll.push(neighbor);
                        q.push(neighbor);
                    }

                    if (parent[neighbor].size()==1 && parent[neighbor][0]==-1)
                        parent[neighbor][0] = node;
                    else
                        parent[neighbor].push_back(node);

                    if (parent_edge[neighbor].size()==1 && parent_edge[neighbor][0]==-1)
                        parent_edge[neighbor][0] = edge_id;
                    else
                        parent_edge[neighbor].push_back(edge_id);

                    if (used_channels[neighbor].size()==1 && used_channels[neighbor][0]==-1)
                        used_channels[neighbor][0] = current_channel;
                    else
                        used_channels[neighbor].push_back(current_channel);
                }
                else
                {
                    if(node == service.start)
                    {
                        // 找到可选择的最窄的范围通道
                        int ch = findShortestRangeChannel(edge.channels, service.width);
                        if(ch != -1)
                        {
                            if(isQEleRepeat(qAll, neighbor) == false)
                            {
                                qAll.push(neighbor);
                                q.push(neighbor);
                            }

                            if (parent[neighbor].size()==1 && parent[neighbor][0]==-1)
                                parent[neighbor][0] = node;
                            else
                                parent[neighbor].push_back(node);

                            if (parent_edge[neighbor].size()==1 && parent_edge[neighbor][0]==-1)
                                parent_edge[neighbor][0] = edge_id;
                            else
                                parent_edge[neighbor].push_back(edge_id);

                            // 选择新通道
                            if (used_channels[neighbor].size()==1 && used_channels[neighbor][0]==-1)
                                used_channels[neighbor][0] = ch;
                            else
                                used_channels[neighbor].push_back(ch);
                            break;
                        }
                    }
                    else
                    {
                        if ((nodes[node].channel_change_capacity - nodes[node].usedChannelCnt) > 0)
                        {
                            // 找到可选择的最窄的范围通道
                            int ch = findShortestRangeChannel(edge.channels, service.width);
                            if(ch != -1)
                            {
                                if (isChannelAvailable(edge, ch, ch + service.width - 1))
                                {
                                    if(isQEleRepeat(qAll, neighbor) == false)
                                    {
                                        qAll.push(neighbor);
                                        q.push(neighbor);
                                    }

                                    if (parent[neighbor].size()==1 && parent[neighbor][0]==-1)
                                        parent[neighbor][0] = node;
                                    else
                                        parent[neighbor].push_back(node);

                                    if (parent_edge[neighbor].size()==1 && parent_edge[neighbor][0]==-1)
                                        parent_edge[neighbor][0] = edge_id;
                                    else
                                        parent_edge[neighbor].push_back(edge_id);

                                    // 选择新通道
                                    if (used_channels[neighbor].size()==1 && used_channels[neighbor][0]==-1)
                                        used_channels[neighbor][0] = ch;
                                    else
                                        used_channels[neighbor].push_back(ch);
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // 规划失败
    if (parent[service.end][parent[service.end].size()-1] == -1)  // 无法到达目标
    {
        // 业务重新规划失败，标记为死亡，死亡的业务占用的通道资源以及变节点次数均不会释放，之后也不会对其进行重新规划
        // 还原-在BFS算法开始之前对业务老路径释放的通道资源情况
        // 并且对该规划失败的业务标记死亡
        restoreOldPathResources(service);

        // 尝试反向的二次规划
        if(bfsTimes == 0)
        {
            bfsTimes = 1;
            service.isDie = false;
            swap(service.start, service.end);
            if(bfsRePlanService3(service, oldServices))
            {
                // 二次规划成功
                swap(service.start, service.end);
                return true;
            }
            swap(service.start, service.end);
        }
        return false;
    }


    // 新路径情况
    vector<int> new_path;
    vector<pair<int, int>> new_channels;
    vector<int> newChangeChannelNodes;
    vector<int> newPathNodes;

    vector<int> pathNodes;
    vector<int> pathEdges;
    vector<int> pathChan;
    // 找到路径了
    if(findPath(service.end, service, pathNodes, pathEdges, pathChan, parent, parent_edge, used_channels))
    {
        new_path = pathEdges;
        newPathNodes = pathNodes;
        if(bfsTimes==0)
        {
            reverse(new_path.begin(), new_path.end());
            reverse(newPathNodes.begin(), newPathNodes.end());
            for(int i = pathChan.size()-1; i>=0; i--)
            {
                new_channels.push_back(make_pair(pathChan[i], pathChan[i] + service.width - 1));
            }
        }
        else
        {
            // 当前是业务首尾反向得到的状态，不需要进行reverse等相关操作
            for(int i = 0; i<=pathChan.size()-1; i++)
            {
                new_channels.push_back(make_pair(pathChan[i], pathChan[i] + service.width - 1));
            }
        }
    }
    else
    {
        // 没有找到路径
        // 还原-释放老路径通道占用情况
        restoreOldPathResources(service);
        return false;
    }


    // 比对该业务新老路径资源
    // 1.先判断是否使用了相同的边上的，共有的资源通道
    // repeatedEdges 存储了相同边的编号
    vector<int> repeatedEdges;
    repeatedEdges = findCommonElements(new_path,service.path);
    for(int i = 0;i<repeatedEdges.size();i++)
    {
        int commonElement = repeatedEdges[i];
        // 获得老路径 与 新路径 共有边分别在各自 path中的索引值
        pair<int, int> indices = findCommonElementIndices(service.path,new_path,commonElement);
        // commonElement --> new_path in indices.first
        // commonElement --> service.path in indices.second
        if (indices.first != -1 && indices.second != -1)
        {
            pair<int,int> result = removeOverlap(service.channels[indices.first],new_channels[indices.second]);
            // 完全不重叠 or 部分重叠
            if(result.first != -1 && result.second != -1)
            {
                // result 即 该业务老路径上 这条边上的 剩余资源
                service.channels[indices.first] = result;
            }
            else
            {
                // 完全覆盖---这条共有边上老路径所使用的通道资源，被新路径完全使用
                // 将这条边，在老路径中剔除
                service.path.erase(service.path.begin() + indices.first);
                service.channels.erase(service.channels.begin() + indices.first);
            }
        }
    }
    // 2.判断是否对相同的节点使用了变通道次数
    // 同时新路径上使用了变通道能力的节点，次数进行更新
    for(int i = 0;i<new_channels.size()-1;i++)
    {
        if(new_channels[i] != new_channels[i+1])
        {
            ++nodes[newPathNodes[i+1]].usedChannelCnt;
            newChangeChannelNodes.push_back(newPathNodes[i+1]);
        }
    }
    // 判断新老路径上是否对同一个节点使用了变通道的次数
    vector<int> repeatedChangeChannelNodes;
    repeatedChangeChannelNodes = findCommonElements(newChangeChannelNodes,service.changeChannelNodes);
    // 将service.changeChannelNodes 中 被新路径使用的变通道节点能力的节点去除
    if(repeatedChangeChannelNodes.size() != 0)
    {
        removeElements(service.changeChannelNodes,repeatedChangeChannelNodes);
    }
    // 将该业务老路径剩余的资源进行占用
    oldServices[service.id] = Service(service.id,service.start,service.end,service.width,service.value);
    oldServices[service.id].path = service.path;
    oldServices[service.id].channels = service.channels;
    oldServices[service.id].changeChannelNodes = service.changeChannelNodes;
    oldServices[service.id].edge_nums = service.path.size();
    // 将老路径剩余资源占用
    for (int i = 0; i < oldServices[service.id].path.size(); ++i)
    {
        updateChannelOccupation(edges[oldServices[service.id].path[i]], oldServices[service.id].channels[i].first,
                                oldServices[service.id].channels[i].second, true); // 占用的通道资源
    }
    // 占用老路径的剩余节点使用的变通道情况
    for(int i = 0;i<oldServices[service.id].changeChannelNodes.size();i++)
    {
        ++nodes[oldServices[service.id].changeChannelNodes[i]].usedChannelCnt;
    }

    //-------------------------------
    // 对重新规划的新路径通道进行占用
    for (int i = 0; i < new_path.size(); ++i)
    {
        updateChannelOccupation(edges[new_path[i]], new_channels[i].first, new_channels[i].second, true);
        edges[new_path[i]].passServices.insert(service.id);
    }


    service.path = new_path;
    service.channels = new_channels;
    // 更新路径上那些节点使用了变通道
    service.changeChannelNodes = newChangeChannelNodes;
    // 更新经过的节点
    service.pathNodes = newPathNodes;

    // 更新业务的经边数量
    service.edge_nums = new_path.size();


    return true;
}

// 寻找最小范围的插入通道(返回通道范围的左边界索引，为-1则没有)
int Graph::findShortestRangeChannel(const vector<bool> &vec, int width)
{
    int n = vec.size() - 1;
    int min_range_index = -1;
    vector<pair<int, int>> rangVec;

    for (int l = 1; l <= n - width + 1; ++l)
    {
        if (vec[l] == false)
        {
            int r = l;
            while (r <=n && vec[r] == false)
            {
                ++r;
            }
            int length = r - l;
            if(length >= width)
            {
                rangVec.push_back(make_pair(l,r-1));
            }
            l = r;
        }
    }

    if(rangVec.size() > 0)
    {
        // 排序
        sort(rangVec.begin(), rangVec.end(), [](auto a, auto b){
            return (a.second - a.first) < (b.second - b.first);
        });
        min_range_index = rangVec[0].first;
    }

    return min_range_index;
}

2.主函数

int main()
{
    Graph graph;
    graph.initialize();

    // 处理故障和业务重规划
    int T;
    cin >> T;
    while (T--)
    {
        int edgeFailed;  // 之前使用全局变量代替
        while (cin >> edgeFailed && edgeFailed != -1)
        {
            // 标记业务故障边
            graph.markFaultyEdge(edgeFailed);

            // 分析受影响的业务编号
            unordered_set<int> affected_services_set = graph.edges[edgeFailed].passServices;
            // 业务按照价值进行降序排序---------------------------
            vector<int> affected_services(affected_services_set.begin(),affected_services_set.end());
            sort(affected_services.begin(), affected_services.end(), [&graph](int a, int b) {
        
            // 实现业务重规划逻辑
            vector<int> rePlanned_servicesId; // 记录重新规划成功的业务id
            map<int, Service> oldServices;  // 存储业务老路径占用的资源
            for (int service_id : affected_services)
            {
                Service& service = graph.services[service_id];

                bfsTimes = 0;
                // 业务重新规划成功
                if(graph.bfsRePlanService3(service,oldServices))
                {
                    // 将规划成功的业务id 记录至 rePlanned_servicesId中
                    rePlanned_servicesId.push_back(service_id);
                }
                else
                {
                    // bfs规划失败
                    // 使用dfs进行二次规划
                    if(graph.dfsRePlanService(service,oldServices))
                    {
                        service.isDie = false;
                        rePlanned_servicesId.push_back(service_id);
                    }
                }
            }

            // 输出重新规划的业务详情
            graph.displayReplanServicesInfo(rePlanned_servicesId);

            // 对老路径剩余的资源进行释放
            graph.freeOldPathResources(oldServices);
        }
        // 重置图状态以处理下一个场景
        graph.resetGraphState();
    }

    return 0;
}

六、复赛AdvanceV3

复赛相较于初赛的添加部分如下图：

意思是我们赛题组官方写了一份代码，我们需要自己提供一部分测试用例，与官方的测试用例结合，一起输入到我们自己的算法与官方的算法进行比较，得分为所有测试用例我们比官方高的分之和（找到官方算法的瓶颈用例）

赛题组的算法没有考虑变通道，只是找了最短路径（重点），因此我们可以这样分析：

设计关键断点：找出那些可能导致多条业务路径中断的关键边，特别是那些在多条最短路径中都会出现的边。通过断开这些边，可以使得依赖于最短路径的业务受到影响

但是由于课题组时间的安排，最后我复赛没有准备，在正式复赛那天，仅随机生成了30组满足要求的测试用例上传

1.随机生成测试用例

头文件：

Graph
{
public:
    ......
    // 生成测试场景
    static void GenerateTestScenarios(int T1, int minLength, int maxLength, int maxValue, std::vector<std::set<int>> &sequences);
    // 生成随机序列
    static std::set<int> generateRandomSequence(int minLength, int maxLength, int maxValue);
    // 计算相似度
    static double jaccardSimilarity(const std::set<int>& set1, const std::set<int>& set2);
}

源文件：

// 计算Jaccard相似度
double Graph::jaccardSimilarity(const std::set<int>& set1, const std::set<int>& set2)
{
    std::vector<int> intersection;
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(intersection));

    std::vector<int> unionSet;
    std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(unionSet));

    return static_cast<double>(intersection.size()) / unionSet.size();
}

// 生成随机序列
std::set<int> Graph::generateRandomSequence(int minLength, int maxLength, int maxValue)
{
    int randNum = std::rand();
    // cout << "randNum: " << randNum << endl;
    int length = minLength + randNum % (maxLength - minLength + 1);
    // cout << "length: " << randNum % (maxLength - minLength + 1) << endl;
    std::set<int> sequence;

    while (sequence.size() < length) {
        sequence.insert(std::rand() % maxValue + 1);
    }

    return sequence;
}

// 生成测试场景
void Graph::GenerateTestScenarios(int T1, int minLength, int maxLength, int maxValue, std::vector<std::set<int>> &sequences)
{
    // cout << "maxLength: " << maxValue <<endl;
    int maxT1 = 30;
    // T1也是随机生成
    if(T1 < 0)
    {
        // 随机生成T1
        // 使用当前时间作为随机数种子
        std::srand(static_cast<unsigned int>(std::time(nullptr)));
        // 生成一个随机整数
        int randomNumber = std::rand() % maxT1;

        // 生成满足条件的序列
        for (int i = 0; i < randomNumber; ++i) {
            std::set<int> newSequence;
            bool isValid;

            do {
                isValid = true;
                newSequence = generateRandomSequence(minLength, maxLength, maxValue);

                for (const auto& sequence : sequences) {
                    if (jaccardSimilarity(sequence, newSequence) > 0.5) {
                        isValid = false;
                        break;
                    }
                }
            } while (!isValid);

            sequences.push_back(newSequence);
        }

    }
    else
    {
        std::srand(static_cast<unsigned int>(std::time(nullptr)));
        // cout << "T1: " << T1 << endl;
        // 生成满足条件的序列
        for (int i = 0; i < T1; ++i) {
            std::set<int> newSequence;
            bool isValid;

            do {
                isValid = true;
                newSequence = generateRandomSequence(minLength, maxLength, maxValue);

                for (const auto& sequence : sequences) {
                    if (jaccardSimilarity(sequence, newSequence) > 0.5) {
                        isValid = false;
                        break;
                    }
                }
            } while (!isValid);

            sequences.push_back(newSequence);
        }
    }
}

2.主函数

int main()
{
    Graph graph;
    graph.initialize();

    int T1 = 30;
    int minLength = min(M,60)/2;
    int maxLength = min(M,60);
    Graph::GenerateTestScenarios(T1, minLength, maxLength, M, graph.sequences);


    cout << graph.sequences.size() << endl;
    for(auto &setEle: graph.sequences)
    {
        cout << setEle.size() <<endl;
        for(auto &ele : setEle)
        {
            cout << ele << " ";
        }
        cout << endl;
    }

    // 处理故障和业务重规划
    int T;
    cin >> T;
    while (T--)
    {
        int edgeFailed;  // 之前使用全局变量代替
        while (cin >> edgeFailed && edgeFailed != -1)
        {
            // 标记业务故障边
            graph.markFaultyEdge(edgeFailed);

            // 分析受影响的业务编号
            unordered_set<int> affected_services_set = graph.edges[edgeFailed].passServices;
            // 业务按照价值进行降序排序---------------------------
            vector<int> affected_services(affected_services_set.begin(),affected_services_set.end());
            sort(affected_services.begin(), affected_services.end(), [&graph](int a, int b) {
                return graph.services[a].value > graph.services[b].value;  // 更改比较逻辑以实现降序
            });

            // 实现业务重规划逻辑
            vector<int> rePlanned_servicesId; // 记录重新规划成功的业务id
            map<int, Service> oldServices;  // 存储业务老路径占用的资源
            for (int service_id : affected_services)
            {
                Service& service = graph.services[service_id];

                bfsTimes = 0;
                // 业务重新规划成功
                if(graph.bfsRePlanService3(service,oldServices))
                {
                    // 将规划成功的业务id 记录至 rePlanned_servicesId中
                    rePlanned_servicesId.push_back(service_id);
                }
                else
                {
                    // bfs规划失败
                    // 使用dfs进行二次规划
                    if(graph.dfsRePlanService(service,oldServices))
                    {
                        service.isDie = false;
                        rePlanned_servicesId.push_back(service_id);
                    }
                }
            }

            // 输出重新规划的业务详情
            graph.displayReplanServicesInfo(rePlanned_servicesId);

            // 对老路径剩余的资源进行释放
            graph.freeOldPathResources(oldServices);
        }
        // 重置图状态以处理下一个场景
        graph.resetGraphState();
    }

    return 0;
}