图的邻接表边的权值问题

Question

给定一个n个节点m条边的带权有向图G，节点编号从1到n，图中可能有重边。

如果从节点u到节点v有一条权值为w的有向边，我们称这条边为(u,v,w)。

现在，你要将所有w为3的倍数的边(u,v,w)拆分，即删掉这条边，然后添加两条边(u,v,2w/3)和(v,u,w/3)。重复这个过程，直到所有边的权值都不是3的倍数。

图的定义如下：

// 邻接表中的边结构体
struct Edge {
    int to;         // 目标节点
    int weight;     // 权重
    Edge(int t, int w) : to(t), weight(w) {}
};
 
// 邻接表中的节点结构体
struct Node {
    int val;                // 节点的值
    vector<Edge> neighbors; // 邻居节点
    Node(int v) : val(v) {}
};
 
// 图的邻接表结构体
struct Graph {
    vector<Node> nodes;     // 节点集合
    Graph(int n) {
        for (int i = 0; i <= n; i++) {
            nodes.push_back(Node(i));
        }
    }
};

请问如何实现将所有w为3的倍数的边(u,v,w)拆分？

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

解决方案

根据问题描述，我们需要将所有权值为3的倍数的边(u,v,w)拆分。我们可以使用邻接表来存储图的边信息。

首先，我们遍历图中的每条边，如果边的权值为3的倍数，我们就将边拆分成多条边，每条边的权值为1。

下面是一个示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v, w;
};

vector<Edge> edges;
vector<vector<Edge>> graph;

void splitEdges(int n) {
    for (int i = 0; i < edges.size(); i++) {
        Edge& e = edges[i];
        if (e.w % 3 == 0) {
            int count = e.w / 3;
            for (int j = 0; j < count; j++) {
                Edge newEdge = {e.u, e.v, 1};
                graph[e.u].push_back(newEdge);
                graph[e.v].push_back(newEdge);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    graph.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        Edge e = {u, v, w};
        edges.push_back(e);
        graph[u].push_back(e);
    }
    splitEdges(n);
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << "Node " << i << " has edges:" << endl;
        for (const auto& e : graph[i]) {
            cout << "(" << e.u << ", " << e.v << ", " << e.w << ")" << endl;
        }
    }
    return 0;
}

在上面的代码中，我们首先读入图的节点数和边数，然后遍历每条边，如果边的权值为3的倍数，我们就将边拆分成多条边，每条边的权值为1。最后，我们输出结果。

注意：在上面的代码中，我们假设图中可能有重边，但是实际上我们可以使用哈希表来存储边的信息，以避免重边的问题。