传染病控制Python题解

代码参考https://blog.csdn.net/qq_47780707/article/details/122612528

n,p=map(int,input().split())
#链接表的第一个数组不用 因为没有节点0
linkedlist=[[] for _ in range(n+1)] 
for _ in range(p):
    x,y=map(int,input().split())
    linkedlist[x].append(y)
    linkedlist[y].append(x)
#print (linkedlist)
#构造树其中i结点的子结点为root[i]
tree=[[]for _ in range(n+1)] #第一个数组不用

def createTree(root):
    if len(linkedlist[root])!=0:
        tree[root]=linkedlist[root][:]
        for x in linkedlist[root]:
            linkedlist[x].remove(root)
            createTree(x)
createTree(1)

#print(tree)
bestresult=300
#输入当前层结点和当前感染人数，计算从下一层开始的被感染的最少人数并返回人数
def dfs(currentlayer,currentcount): #此函数第一个参数为列表，第二个参数为一个int值
    global tree,bestresult
    nextlayer=[]
    for x in currentlayer:
        nextlayer+=tree[x] #列表相加
    minnum=300
    #到达叶子结点，更新bestresult
    if nextlayer==[]:
        if currentcount<bestresult:
            bestresult=currentcount
        return 0
    #若感染人数大于bestresult则剪枝
    elif currentcount+len(nextlayer)-1<bestresult: 
        for i,x in enumerate(nextlayer):#i表示索引 x表示nextlayer[i]
            del nextlayer[i]
            nextnum=dfs(nextlayer,currentcount+len(nextlayer)-1)
            if minnum>nextnum:
                minnum=nextnum
            nextlayer.insert(i,x)
        return len(nextlayer)-1+minnum
    #若大于则直接返回300，即表示剪枝
    else:
        return 300
    
#最后加的1是加上原本就被感染的根节点
print(dfs([1],1)+1)