Partition Magic

Limits: 10s, 32 MB

The Great Researcher Dr. Bari loves to do research. Once he was doing research on VLSI Circuit Design and came to know about graph partitioning. In graph partitioning problem, you are given an undirected graph G with V vertices and E edges. The weights on the edges E are also given. You have to partition V into two disjoint subsets A and B of equal size in such a way, that the sum of the weights of the subset of edges that cross from A to B is minimized.


This is a companion discussion topic for the original entry at https://toph.co/p/partition-magic