假设我们有两个组，女人和男人每个女人都有自己感兴趣的男人我们将它们的兴趣表示为二分图中的边。
现在，我们正在试着把大家安排在圆桌会议上，比如如果你围着桌子转，每一个座位都会有一对座位会被一对有连接的夫妇占用所以，如果你顺时针旋转桌子，例如，一个座位可能有一个女人对坐在下一个座位上的男人感兴趣，而这也可能是坐在下一个座位上的女人感兴趣，等等每张桌子至少要有k个客人。
我正试图设计一个使用最大流的算法来满足这些要求，我会非常感谢一些想法
最佳答案
这个问题一般是np难的。假设你有一个有2n个节点的图，你只有一个2n大小的表，现在，有一种方法可以让每个人都按照你想要的方式坐在这个表的周围，只要这个图有一个哈密顿循环。由于二部图上的哈密顿循环问题是NP难的，所以你的问题也是NP难的因此，我怀疑有一个很好的方法可以使用max-flow来解决这个特殊的问题，除非您构建了一个指数级的大型图。
关于algorithm - 圆 table 两人座位安排，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36414921/