# C ++: fast algorithm to find minimum sum of loop edges

I have an undirected weighted graph and want to find the minimum sum of all cycles. This means that if I have no loop, the answer will be 0. If I have one loop, the answer will be the minimum weight of the edge of that loop. And if I have more than one cycle, this is the sum of these minimum weights.

My algorithm that I have implemented uses some kind of Prims algorithm. I just add the heaviest edges, and when the loop is formed, the weight is added to the answer.

I thought it was correct as all my test cases show the correct answer.

But there must be a mistake somewhere, I just couldn't find it.

``````struct connection {
int a, b, cost;

bool operator<(const connection rhs) const {
return cost < rhs.cost || (cost == rhs.cost && (a < rhs.a || (a == rhs.a && b < rhs.b)));
}
};

int n, m, researchers; // Amount of vertices, edges
std::list<int> *used;
std::set<connection> priorityQ;

void addEdge(int v, int w, int cost) {
connection temp;
temp.a = v;
temp.b = w;
temp.cost = cost;
temp.a = w;
temp.b = v;
}

bool isUsed(int u, int v) {
for (std::list<int>::iterator it = used[u].begin(); it != used[u].end(); ++it) {
int te = *it;
if (te == v) return true;
}
return false;
}

void expand(int u) {

connection v = *it;

if (isUsed(u, v.b)) continue;

used[v.b].push_back(u);
used[u].push_back(v.b);

priorityQ.insert(v);
}
}

void PrimR(int u, bool added[]) {
expand(u);
}

// Prim algorithm
void Prim(int u, bool added[]) {

expand(u);

while (priorityQ.size() > 0) {
connection now = *priorityQ.rbegin();
priorityQ.erase(*priorityQ.rbegin());

researchers += now.cost;
}
else {

}
}

}

int main()
{

int t;

// loop over all test cases
scanf("%d ", &t);
for (int i = 1; i <= t; i++) {

// read input nodes n, connections m
scanf("%d %d", &n, &m);

for (int j = 0; j < m; j++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
addEdge(a - 1, b - 1, c);
}

researchers = 0;

// Use of prim with heaviest edges first
used = new std::list<int>[n];

for (int j = 0; j < n; j++) {
}

for (int j = 0; j < n; j++) {
}
}

// print desired output
printf("Case #%d: %d\n", i, researchers);

delete[] used;
}
return 0;
}
```

```

Do you know what I am doing wrong?

+3

source to share

I didn't think there could be multiple connections between two nodes.

My next code solves the following:

``````struct connection {
int a, b, cost, id;

bool operator<(const connection rhs) const {
return cost < rhs.cost || (cost == rhs.cost && id < rhs.id);
}
};

int n, m, researchers; // Amount of vertices, edges
std::set<connection> priorityQ;

void addEdge(int v, int w, int cost, int id) {
connection temp;
temp.a = v;
temp.b = w;
temp.cost = cost;
temp.id = id;
temp.a = w;
temp.b = v;
}

void deleteEdge(int v, int w, int id) {
if ((*it).id == id) {
break;
}
}
if ((*it).id == id) {
break;
}
}
}

void expand(int u) {

connection v;
v.a = (*it).a < (*it).b ? (*it).a : (*it).b;
v.b = (*it).a < (*it).b ? (*it).b : (*it).a;
v.cost = (*it).cost;
v.id = (*it).id;

priorityQ.insert(v);
}
}

void PrimR(int u, bool added[]) {
expand(u);
}

// Prim algorithm
void Prim(int u, bool added[]) {

expand(u);

while (priorityQ.size() > 0) {
connection now = *priorityQ.rbegin();
priorityQ.erase(*priorityQ.rbegin());

deleteEdge(now.a, now.b, now.id);

researchers += now.cost;
}
}
}
}

}

int main()
{

int t;

// loop over all test cases
scanf("%d ", &t);
for (int i = 1; i <= t; i++) {

// read input nodes n, connections m
scanf("%d %d", &n, &m);

for (int j = 0; j < m; j++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);

addEdge(a - 1, b - 1, c, j);
}

researchers = 0;

// Use of prim with heaviest edges first

for (int j = 0; j < n; j++) {
}

for (int j = 0; j < n; j++) {
}
}

// print desired output
printf("Case #%d: %d\n", i, researchers);

}
return 0;
}
```

```
0

source

All Articles