Я пытаюсь решить модификацию следующей задачи: 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). Выходные данные должны выводить двоичное представление суммы всех кратчайших путей.
Мое решение : я получил один из кодов, предоставленных в связанном вопросе, и выполнил алгоритм Крускала, чтобы получить все кратчайшие пути.
Моя проблема : Я не могу найти способ хранения весов 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();
}