You are given a graph, Each edge has a weight, and the goal is to find the maximum spanning bipartite graph.

First I want to solve this problem like MST with gready, and with 2-SAT. But if we have a graph like this: 6 9 1 2 2 1 3 1 2 3 1 1 4 1 2 4 1 1 5 1 2 5 1 1 6 1 2 6 1 You will fail. You can't choose 1 2 2 be cause you will earn 2 and lost 4.

How can I solve this problem. Please help me and sorry for my bad English.