图论:完全匹配

Question

的问题是：儿童在很小的时候就开始对某些玩具和活动产生偏好。由于不同玩具的数量减少，托儿所正在寻找一种方式来满足儿童的口味，在儿童娱乐时间的最佳方式。因此，考虑到学校里每个孩子都喜欢的玩具列表，你应该用图表来找出能够同时玩任何感兴趣的玩具的孩子的最大数量。

条目第一行包含三个整数N (1≤N≤100)、M (1≤M≤100)和L (0≤L≤10,000)，分别代表托儿所的儿童人数、玩具数量和学生感兴趣的玩具总数。每个孩子被一个从0到N1的整数唯一地标识出来，每个玩具被一个从0到M1的整数唯一识别。下一个L行中的每一行都包含两个整数c和b，表示一个孩子c喜欢玩玩具b。输出你的程序应该打印一行，其中包含可以同时玩任何你喜欢的玩具的孩子的最大数量。

INPUT EXAMPLE: 
 3 4 6
 0 0
 0 2
 0 3
 1 1
 2 1
 2 3

 Output
 3

我的解决方案：

class Graph: 
def __init__(self,_childs,_toys):
    toys = _toys*[0]
    self.graph = _childs*[toys]
    self.childs = _childs
    self.toys = _toys

def add_match(self,child,toy):
    self.graph[child][toy] = 1

def perfect_match(self, l, myToys, match): 
    for r in range(self.toys): 
      if self.graph[l][r] and match[r] == False: 
        match[r] = True
        if myToys[r] == -1 or self.perfect_match(myToys[r],myToys, match): 
          myToys[r] = l
          return True
    return False

def max_match(self):
    myToys = [-1] * self.toys
    result = 0
    for i_child in range(self.childs):
      match = [False] * self.toys
      if self.perfect_match(i_child, myToys, match):
        result += 1
    return result


g1 = Graph(3,4)
g1.add_match( 0 , 0 )
g1.add_match( 0 , 2 )
g1.add_match( 0 , 3 )
g1.add_match( 1 , 1 )
g1.add_match( 2 , 1 )
g1.add_match( 2 , 3 )
print(g1.max_match())
# output = 3

g2 = Graph(5,5)
g2.add_match( 0 , 1 )
g2.add_match( 0 , 2 )
g2.add_match( 1 , 1 )
g2.add_match( 2 , 0 )
g2.add_match( 2 , 3 )
g2.add_match( 3 , 3 )
g2.add_match( 4 , 3 )
print(g2.max_match())
# output = 4

但是我在一些测试中失败了：(我没有资格测试，我只是想要这个解决方案得到52%的分数，所以也许只是解决一些输入特殊情况.)

enter code here
Test 6
WRONG
Test 7
WRONG
Test 8
WRONG
Test 9
WRONG

Test 12
WRONG
Test 13
WRONG
Test 14

Test 22
WRONG
Test 23
WRONG
Test 24
WRONG

Answer 1

我认为这个问题使用了一个简单的观察。如果有两个孩子，第一个只喜欢2个玩具，第二个喜欢20个玩具，那么你会贪婪地给第一个孩子分配一个玩具，然后再给第二个孩子分配一个玩具(因为他有更多的选择)。

将此属性与回溯一起使用以解决问题。