Hello everyone! There is a problem in an Olympiad from my country 5 years ago, but I could not solve it, nor some of my friends. So I wanted to ask for help with this problem. The problem is as follows:↵
↵
Given a bipartite graph with $n$ nodes on the left side and $m$ nodes on the right side. There is also a weight matrix $C$, $C_{i,j}$ is the weight of the edge connecting the $i$-th node on the left side to the $j$-th node on the right side. The problem ask to find a sub-tree of the graph with minimum total edge weight and it connects every nodes on the left side. In other word, we need to find a minimum [Steiner tree][Steiner-tree], whose terminals are nodes on the left side.↵
↵
Constraints: $n, m \le 1000$. $-1 \le C_{i, j} \le 10000$. $C_{i, j} = -1$ means there is no edge connecting the $i$-th node on the left side and $j$-th node on the right side (or it can be considered $+\infty$).↵
↵
Here is the samples from the problem statement.↵
↵
<spoiler summary="Sample 1">↵
↵
Input (the first line contains $n$ and $m$)↵
↵
```↵
4 3↵
0 -1 5↵
0 4 4↵
-1 0 -1↵
1 2 0↵
```↵
↵
Optimal answer: the cost will be $3$. Besides using all edges with $0$ cost, we use the edges $(4,1)$ (cost =weights $1$) and $(4,2)$ (cost =weights $2$).↵
↵
</spoiler>↵
↵
<spoiler summary="Sample 2">↵
Input (the first line contains $n$ and $m$)↵
↵
```↵
4 4↵
0 -1 5 3↵
-1 4 5 -1↵
-1 0 -1 0↵
6 6 0 -1↵
```↵
</spoiler>↵
↵
Also some _interseting_ examples that my friend has drawn:↵
↵
<spoiler summary="Friend's graph 1">↵
↵
</spoiler>↵
↵
↵
[Steiner-tree]: https://en.wikipedia.org/wiki/Steiner_tree_problem↵
Besides edges with weight $0$, we can use the edges $(1, 4)$ (weights $3$), $(2, 2)$ (weights $4$), and $(1, 3)$ (weights $5$).↵
</spoiler>↵
↵
Also some _interseting_ examples that my friend has drawn:↵
↵
<spoiler summary="Friend's graph 1">↵
<img src="/predownloaded/64/ec/64ecaf71c721b9a3f774d4314fec40fe8e686c32.png" />↵
↵
This graph shows that plain Kruskal/Prim does not work.↵
</spoiler>↵
↵
<spoiler summary="Friend's graph 2">↵
↵
<img src="/predownloaded/00/ad/00ad90233bd37f966509859c93253b08f303b2b8.png" />↵
↵
</spoiler>↵
↵
I have done some Googling, but it's no good. I have found a Wikipedia article called [Quasi bipartitie graph][Quasi-bipartitie-graph] and there were only approximating solutions. But I'm not sure if this article has anything to do with this problem.↵
↵
Please help me find a solution to this problem, or maybe help me prove this is an NP problem, because I'm really depressed :(.↵
↵
[Steiner-tree]: https://en.wikipedia.org/wiki/Steiner_tree_problem↵
[Quasi-bipartitie-graph]: https://en.wikipedia.org/wiki/Quasi-bipartite_graph
↵
Given a bipartite graph with $n$ nodes on the left side and $m$ nodes on the right side. There is also a weight matrix $C$, $C_{i,j}$ is the weight of the edge connecting the $i$-th node on the left side to the $j$-th node on the right side. The problem ask to find a sub-tree of the graph with minimum total edge weight and it connects every nodes on the left side. In other word, we need to find a minimum [Steiner tree][Steiner-tree], whose terminals are nodes on the left side.↵
↵
Constraints: $n, m \le 1000$. $-1 \le C_{i, j} \le 10000$. $C_{i, j} = -1$ means there is no edge connecting the $i$-th node on the left side and $j$-th node on the right side (or it can be considered $+\infty$).↵
↵
Here is the samples from the problem statement.↵
↵
<spoiler summary="Sample 1">↵
↵
Input (the first line contains $n$ and $m$)↵
↵
```↵
4 3↵
0 -1 5↵
0 4 4↵
-1 0 -1↵
1 2 0↵
```↵
↵
Optimal answer: the cost will be $3$. Besides using all edges with $0$ cost, we use the edges $(4,1)$ (
↵
</spoiler>↵
↵
<spoiler summary="Sample 2">↵
Input (the first line contains $n$ and $m$)↵
↵
```↵
4 4↵
0 -1 5 3↵
-1 4 5 -1↵
-1 0 -1 0↵
6 6 0 -1↵
```↵
↵
Also some _interseting_ examples that my friend has drawn:↵
↵
<spoiler summary="Friend's graph 1">↵
↵
</spoiler>↵
↵
↵
[Steiner-tree]: https://en.wikipedia.org/wiki/Steiner_tree_problem
Besides edges with weight $0$, we can use the edges $(1, 4)$ (weights $3$), $(2, 2)$ (weights $4$), and $(1, 3)$ (weights $5$).↵
</spoiler>↵
↵
Also some _interseting_ examples that my friend has drawn:↵
↵
<spoiler summary="Friend's graph 1">↵
<img src="/predownloaded/64/ec/64ecaf71c721b9a3f774d4314fec40fe8e686c32.png" />↵
↵
This graph shows that plain Kruskal/Prim does not work.↵
</spoiler>↵
↵
<spoiler summary="Friend's graph 2">↵
↵
<img src="/predownloaded/00/ad/00ad90233bd37f966509859c93253b08f303b2b8.png" />↵
↵
</spoiler>↵
↵
I have done some Googling, but it's no good. I have found a Wikipedia article called [Quasi bipartitie graph][Quasi-bipartitie-graph] and there were only approximating solutions. But I'm not sure if this article has anything to do with this problem.↵
↵
Please help me find a solution to this problem, or maybe help me prove this is an NP problem, because I'm really depressed :(.↵
↵
[Steiner-tree]: https://en.wikipedia.org/wiki/Steiner_tree_problem↵
[Quasi-bipartitie-graph]: https://en.wikipedia.org/wiki/Quasi-bipartite_graph
