我用什么算法来解决这个问题?
What algorithm do I use to solve this?
2016年的UVA编程竞赛题目在这里:http://acm.cs.virginia.edu/data/2016-contest.pdf。
问题我很有趣。问题总结如下。
A restaurant has n types of foods, and m people want to order. Each person wants one of k foods (each of which is listed in the n types before). Each food the restaurant has can only be served once. Is it possible to satisfy everyone?
示例如下:
A restuarant has a pancakes, waffles, and muffins.
Tom wants pancakes.
Suzy wants pancakes or waffles.
Joe wants muffins or waffles.
在这种情况下,每个人都可以满意(汤姆吃煎饼,苏西吃华夫饼,乔吃松饼)。
我将使用什么算法来完全解决这个问题(而不仅仅是简化它)?我在哪里可以找到它的伪代码?
我认为这个问题可以通过使用 Ford-Fulkerson 算法的二分匹配来解决。
可以在此处找到示例和解释 http://www.geeksforgeeks.org/maximum-bipartite-matching/
2016年的UVA编程竞赛题目在这里:http://acm.cs.virginia.edu/data/2016-contest.pdf。
问题我很有趣。问题总结如下。
A restaurant has n types of foods, and m people want to order. Each person wants one of k foods (each of which is listed in the n types before). Each food the restaurant has can only be served once. Is it possible to satisfy everyone?
示例如下:
A restuarant has a pancakes, waffles, and muffins. Tom wants pancakes. Suzy wants pancakes or waffles. Joe wants muffins or waffles.
在这种情况下,每个人都可以满意(汤姆吃煎饼,苏西吃华夫饼,乔吃松饼)。
我将使用什么算法来完全解决这个问题(而不仅仅是简化它)?我在哪里可以找到它的伪代码?
我认为这个问题可以通过使用 Ford-Fulkerson 算法的二分匹配来解决。 可以在此处找到示例和解释 http://www.geeksforgeeks.org/maximum-bipartite-matching/