Problem link (The problem is originally from ONTAK 2007, but I can't find it from szkopul.edu.pl)
Statement: $$$N$$$ people wants to cross the river with a boat. In each step, two people will take the boat to cross the river, and if necessary, one of those two will come back with a boat to salvage the remaining people. Each people have a time factor $$$t_i$$$, and the time boat needs to cross the river is equal to the maximum time factor of all people on the boat. Additionally, there are $$$M$$$ pairs of people, who don't want to be in the boat at the same time. What is the minimum time needed for all people to cross the river? Print
NIE if this is impossible at all. ($$$2 \le N \le 100\,000, 0 \le M \le 100\,000$$$)
I can solve this problem in polynomial time, but I don't think this approach can be optimized, nor have I found any alternative approach.
Construct a graph with $$$N$$$ vertices and $$$N(N-1)/2-M$$$ edges. Edges connect all pairs of people who are ok being in the same boat. Edge $$$e = (i, j)$$$ has a weight $$$t_i + t_j + \max(t_i, t_j)$$$ . We need to select $$$n - 1$$$ edges in the graph, such that each vertex has at least one incident edge that is selected, and the sum of weight is minimized (It's ok to select one edge multiple times). This optimization problem can be reduced into weighted general matching, which can be solved in $$$O(N^3)$$$.
The problem is almost 20 years old, but it's really hard. Anyone knows how to solve this?