Points: 200

Tags: algorithmic 

Poll rating:

We have a set of N friends, and M pairwise connections between friends. Each connection goes both ways, so if, for example, Aariss Weiron is friends with Bendelman, then Bendelman is also friends with Aariss Weiron. Each connection also has an associated weight, representing how close the two friends are, which is a positive integer value. No two pairs of friends with a connection have the same weight.

Our objective is to somehow divide our set of friends into two 'equal' halves. We also want to put friends who are pretty close to each other into the same set. We formally define the problem as follows:

We have a set of friends of even size, some with bi-directional pairwise connections. Each connection has a positive integer weight, and each connection has a distinct weight. Our objective is to divide our friends into two sets of equal size with this property: The largest connection-weight that crosses between the two sets should be as small as possible. Compute this connection-weight for each friend network given. A crossing connection is one such that the two friends it connects are in different sets. Each friend network is in the following format: The first line has two numbers:

N (guaranteed to be even) and M (number of connections). M lines follow this line. Each one represents a connection and has three tokens. The first two are the friends it connects, and the last one is the weight of the connection.

Writeups

ActionRatingAuthor team
Read writeup
not rated
distcc
You need to authenticate and join a team to post writeups