## 1265 - Tour Belt

Moderator: Board moderators

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

### Re: 1265 - Tour Belt

I can't even suggest any solution . Any ideas?

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

### Re: 1265 - Tour Belt

Help, I'm getting WA.
My solution's strategy is this: group edges with same weights.
After that, add heaviest edges. Count sizes of newly formed connected components.
Do the same for all edge groups from heaviest to lightest.
For test cases in the statement I got the same output, but my solution is not passing
all system tests.

Code: Select all

``````#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstring>
#include <climits>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define INF INT_MAX-1
#define SQR(x) ((x)*(x))

using namespace std;

#define vertex_sz_MAX	5001
#define edge_w_MAX		100001

/* ufds */
namespace {
int parent[vertex_sz_MAX];
int size[vertex_sz_MAX];

void init_set() {
for (int i = 0; i < vertex_sz_MAX; ++i) {
parent[i] = i;
size[i] = 1;
}
}
int find_set(int x) {
return x == parent[x] ? x : parent[x] = find_set(parent[x]);
}
/* keeps track about newly formed components */
void join_set(int x, int y, set<int> & new_comp) {
x = find_set(x);
y = find_set(y);

if (x == y)
return;

if (size[x] > size[y]) {
parent[y] = x;
size[x] += size[y]; new_comp.insert(x);
size[y] = 0; new_comp.erase(y);
} else {
parent[x] = y;
size[y] += size[x]; new_comp.insert(y);
size[x] = 0; new_comp.erase(x);
}
}
}

int vertex_sz, edges_sz, w_max;
list<pair<int, int> > edges[ edge_w_MAX ];

int solve() {
init_set();

set<int> new_comp;
int count = 0;
for (int w = w_max; w >= 1; --w) {
new_comp.clear();

/* add edges with same weights */
for (list<pair<int, int> >::iterator it = edges[w].begin(); it != edges[w].end(); ++it) {
join_set(it->first, it->second, new_comp);
}

for (set<int>::iterator it = new_comp.begin(); it != new_comp.end(); ++it) {
count += size[*it];
}
}

return count;
}

int main() {
int test_n, x, y, w;
cin >> test_n;

while (test_n--) {
/* prepare stage */
w_max = 0;
for (int i = 0; i < edge_w_MAX; ++i)
edges[i].clear();

/* input stage */
cin >> vertex_sz >> edges_sz;
while (edges_sz--) {
cin >> x >> y >> w;
w_max = max(w, w_max);
edges[w].push_back(make_pair(x, y));
}

/* solve and output */
cout << solve() << endl;
}

return 0;
}
``````

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

### Re: 1265 - Tour Belt

For this test case

Code: Select all

``````1
4 6
1 4 1
1 2 2
1 3 3
2 4 4
3 4 5
2 3 6
``````
Solution's out is:

Code: Select all

``````9
``````

fabikw
New poster
Posts: 3
Joined: Tue Oct 28, 2014 1:59 am

### Re: 1265 - Tour Belt

My strategy is the following:
• Sort edges in decreasing order
• For each edge that connects two different components, check if each component is a candidate (this edge less than min edge in the component and size > 1), if so, add its size. Join the components.
• Update the min size of the new component as the minimum of all inside edges (only need to check edges that join the two old components).