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.