优化问题 - 找到最大值

Question

我手边有一个问题,可以简化为这样的事情:

假设在二维平面XY中有一堆随机点,其中对于每个Y,在X上可以有多个点,并且对于每个X,在Y上可以有多个点.

无论何时选择一个点(Xi,Yi),都不能选择X = Xi OR Y = Yi的其他点.我们必须选择最大点数.

Answer 1

这可以简化为简单的最大流量问题.如果你有一个点(xi,yi),在图中它应该用从源S到点xi,从xi到yi以及从yi到最后一个节点(sink)T的路径来表示.

注意,如果我们有点(2,2)和(2,5),那么从S到x2的路径仍然只有一条.所有路径(边)都具有容量1.

这个网络的流程就是答案.

更新
我现在没有图形编辑器可视化问题,但您可以轻松地手动绘制示例.比方说,分数是(3,3)(3,5)(2,5)

然后边(路径)将是
S - > x2,S - > x3
y3 - > T,y5 - > T
x3 - > y3,x3 - > y5,x2 - > y5

流量:S - > x2 - > y5 - > T和S - > x3 - > y3 - > T
从水源到水槽的"水"量为2,答案也是如此.