我正在尝试解决以下问题的修改：https://codereview.stackexchange.com/questions/135915/sum-of-all-paths-between-all-pairs-of-nodes-in-a-tree
问题描述：查找树中所有节点对之间所有最短路径的总和。在输入的第一行中，我们得到两个数字 N 和 M，分别是节点和边的数量。在此之后的 M 行中，我们得到输入 (a，b，c(，其中 a 和 b 是节点，c 是它们之间边的权重。但是实际重量是2^(c(。输出必须打印所有最短路径之和的二进制表示形式。
我的解决方案：我从链接的问题中获得了其中一个代码，我执行了 kruskal 算法来获得所有最短路径。
我的问题：我找不到存储 2^(c( 权重的方法，因为 c 最多为 2*10^(5( - 1。
到目前为止我的代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using namespace std;
#define mp make_pair
#include <math.h> /* pow */
typedef long long ll;
#define MOD 1300031
vector<vector<pair<ll, ll>>> g;
vector<ll> sum1, sum2, cnt;
vector<int> visited;
ll n;
#define edge pair<int,int>
void convertToBinary(unsigned int n)
{
if (n / 2 != 0) {
convertToBinary(n / 2);
}
printf_s("%d", n % 2);
}
class Graph {
private:
vector<pair<int, edge>> G; // graph
vector<pair<int, edge>> T; // mst
int* parent;
int V; // number of vertices/nodes in graph
public:
Graph(int V);
void AddWeightedEdge(int u, int v, int w);
int find_set(int i);
void union_set(int u, int v);
void kruskal();
vector<vector<pair<ll, ll>>> print(vector<vector<pair<ll, ll>>> g);
};
Graph::Graph(int V) {
parent = new int[V];
//i 0 1 2 3 4 5
//parent[i] 0 1 2 3 4 5
for (int i = 0; i < V; i++)
parent[i] = i;
G.clear();
T.clear();
}
void Graph::AddWeightedEdge(int u, int v, int w) {
G.push_back(make_pair(w, edge(u, v)));
}
int Graph::find_set(int i) {
// If i is the parent of itself
if (i == parent[i])
return i;
else
// Else if i is not the parent of itself
// Then i is not the representative of his set,
// so we recursively call Find on its parent
return find_set(parent[i]);
}
void Graph::union_set(int u, int v) {
parent[u] = parent[v];
}
void Graph::kruskal() {
int i, uRep, vRep;
sort(G.begin(), G.end()); // increasing weight
for (i = 0; i < G.size(); i++) {
uRep = find_set(G[i].second.first);
vRep = find_set(G[i].second.second);
if (uRep != vRep) {
T.push_back(G[i]); // add to tree
union_set(uRep, vRep);
}
}
}
vector<vector<pair<ll, ll>>> Graph::print(vector<vector<pair<ll, ll>>> g) {
for (int i = 0; i < T.size(); i++) {
g[T[i].second.first].push_back(mp(T[i].second.second, T[i].first));
g[T[i].second.second].push_back(mp(T[i].second.first, T[i].first));
}
return g;
}
void dfs1(ll node)
{
visited[node] = 1;
for (int i = 0; i < g[node].size(); i++)
{
ll x = g[node][i].first, w = g[node][i].second;
if (visited[x]) continue;
dfs1(x);
sum1[node] += sum1[x] + cnt[x] * w;
cnt[node] += cnt[x];
}
cnt[node]++;
}
void dfs2(ll node)
{
if (node == 1)
{
sum2[node] = sum1[node];
}
visited[node] = 1;
for (int i = 0; i < g[node].size(); i++)
{
ll x = g[node][i].first, w = g[node][i].second;
if (visited[x]) continue;
sum2[x] = sum1[x] + sum2[node] - sum1[x] - cnt[x] * w + w * (n - cnt[x]);
dfs2(x);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
long long int N, M;
cin >> N >> M;
Graph gr(N+1);
for (int i = 0; i < M; i++) {
int u, v, c;
cin >> u >> v >> c;
gr.AddWeightedEdge(u, v, pow(2,c));
}
gr.kruskal();
int t, x, y, w;
n = N;
g.resize(n + 1); sum1.resize(n + 1); sum2.resize(n + 1);
visited.resize(n + 1); cnt.resize(n + 1);
for (int i = 0; i < n - 1; i++)
{
g=gr.print(g);
}
dfs1(1);
visited.clear();
visited.resize(n + 1);
dfs2(1);
double ans = 0;
for (int i = 1; i <= n; i++)
{
ans += (double)sum2[i] / 2;
}
ll fans = (ll)ans;
cout << fans;
sum1.clear(); sum2.clear(); visited.clear(); cnt.clear(); g.clear();
}
首先，请考虑使用另一种命名样式。调用全局变量与成员变量相同的单个字母，但大小写不同(g和G(，类型定义long longll和调用函数dfs1除了你自己之外，任何人都无法读取。
现在进入您的实际问题：如果 c <2 * 10^5，则 log2(c( <18。因此，c 可以存储在任何超过 18 位的整数中。例如 32 位整数。
如果你真的想知道如何在 2 * 10^5
当权重始终为 2^c 时，其二进制表示始终是一个1后跟 c 零(在负 c 的情况下，你会得到分数而不是整数(。所以二进制中的 2^1 是10,2^5 是100000，等等。
知道了这一点，你可以这样打印2^c：
void print_power_of_two(int c)
{
std::puts("1");
for(int i = c; i > 0; --i)
std::puts("0");
}