I nead to solve a problem. Please help me.

Правка en3, от LC20110802, 2024-05-30 14:01:32

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 choose1 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.

Теги graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский LC20110802 2024-05-30 14:03:50 6
en3 Английский LC20110802 2024-05-30 14:01:32 28 Tiny change: 'n```\n6 9\n1 2 2\n1' -> 'n```\n6 9\\n1 2 2\n1'
en2 Английский LC20110802 2024-05-30 13:58:47 15
en1 Английский LC20110802 2024-05-30 13:58:03 499 Initial revision (published)