主页 / 问题 / 1181687
Accepted
Coffee inTime
Asked:2020-09-24 01:44:47 +0000 UTC2020-09-24 01:44:47 +0000 UTC

Python任务市长的命令

  • 772

任何人都可以提出解决问题的算法或代码吗？我在下面附上了我失败的代码。

市长团队 为了确保在选举中获胜，市长决定组建一个他的熟人组成的团队，每个人都是其他人的朋友。知道市长的所有n个熟人之间的关系，创建一个人数最多的团队m。如果有几个解，只推导出一个就足够了。

规格输入 第一行包含市长 n (n < 50) 的熟人数量。第二行包含有友好关系的对 k 的数量。接下来的 k 行包含成对的数字 - 朋友的数量。

输出 第一行包含市长团队的最大组成。下一行包含按人数升序排列的市长团队的组成。

输入数据示例

5
6
1 2
2 3
1 3
3 5
1 5
5 2

输出示例

4
1 2 3 5

我的失败尝试（仅计算正确结果的 44%）：

def foo(couples):
    max_friends = 0
    result = ''
    counter = 0
    while counter < len(couples):
        temp_friends = [couples[counter][0], couples[counter][1]]
        for j in couples:
            if j[0] not in temp_friends:
                for z in temp_friends:
                    if j[0] in temp_friends:
                        break
                    if j == (z, j[0]) or j == (j[0], z): continue
                    if (z, j[0]) in couples or (j[0], z) in couples:
                        temp_friends.append(j[0])

            if j[1] not in temp_friends:
                for z in temp_friends:
                    if j[1] in temp_friends:
                        break
                    if j == (z, j[1]) or j == (j[1], z): continue
                    if (z, j[1]) in couples or (j[1], z) in couples:
                        temp_friends.append(j[1])

        temp_friends.sort()
        if max_friends < len(temp_friends):
            max_friends = len(temp_friends)
            result = " ".join(str(x) for x in temp_friends)
        counter += 1
    print(max_friends)
    print(result)

couples = [(1,2), (2,3), (3,1), (3, 4)]
foo(couples)
python

2 个回答

  1. Best Answer

    应该从图论的角度考虑这项任务（作为显示组中关系的最方便的方法），更具体地说，应该从该理论的派系来考虑。正如维基百科告诉我们的：

    无向图的团是其顶点的子集，其中任意两个顶点由边连接。团是图论的核心概念之一，并用于许多其他数学问题和图构造。团也在计算机科学中进行研究——确定图中是否存在给定大小的团的问题（团问题）是 NP 完全的。尽管有这个困难，许多算法

    那些。我们需要找到什么。让我们回到维基百科：

    Bron-Kerbosh 算法是一种用于查找无向图的所有团（以及最大独立顶点集）的分支定界方法。由荷兰数学家 Bron 和 Kerbosch 于 1973 年开发，它仍然是最有效的团搜索算法之一。

    ПРОЦЕДУРА extend (candidates, not):
  ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates, 
  ВЫПОЛНЯТЬ:
  1 Выбираем вершину v из candidates и добавляем её в compsub
  2 Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v
  3 ЕСЛИ new_candidates и new_not пусты
  4 ТО compsub – клика
  5 ИНАЧЕ рекурсивно вызываем extend (new_candidates, new_not)
  6 Удаляем v из compsub и candidates, и помещаем в not

    效率，我们需要的:)。因此，首先，从收到的数据中，我们为组的所有成员编译一个“关系列表”：

    def foo(couples):
    friendship = {}
    counter = 0
    while counter < len(couples):
        current = couples[counter][0]
        if current not in friendship.keys():
            for a, b in couples:
                if a == current:
                    friendship.setdefault(a, []).append(b)
                if b == current:
                    friendship.setdefault(b, []).append(a)
        counter += 1
    return friendship

    对于这样的输入条件：

    couples = [(1, 2), (2, 3), (1, 6), (2, 6), (1, 3), (3, 5), (1, 5), (5, 2), (6, 4)]

    我们得到：

    {1: [2, 6, 3, 5], 2: [1, 3, 6, 5], 3: [2, 1, 5], 5: [3, 1, 2], 6: [1, 2, 4]}

    现在我们开始按照上面的算法处理生成的数据（代码是老老实实从这里偷来的）：

    def BronKerbosch(P, R=None, X=None):
    P = set(P)
    R = set() if R is None else R
    X = set() if X is None else X
    if not P and not X:
        yield R
    while P:
        v = P.pop()
        yield from BronKerbosch(
            P=P.intersection(n[v]), R=R.union([v]), X=X.intersection(n[v]))
        X.add(v)

    我们剩下的就是得到并给出结果：

    couples = [(1, 2), (2, 3), (1, 6), (2, 6), (1, 3), (3, 5), (1, 5), (5, 2), (6, 4)]
n = foo(couples)
P = n.keys()
res = max(list(BronKerbosch(P)))
print(len(res))
output = " ".join(str(x) for x in res)
print(output)

    结论：

    4
1 2 3 5

    像这样的东西。代码未优化，请勿乱扔拖鞋

    • 3

  2. 在这里，我绘制了一个带有控制台输入的变体。目前尚不清楚您已经可以使用什么。有字典和集合。

    更正

     n = int(input())
 k = int(input())

frends = {} #словарь, ключи - друзья, значения множество друзей. В начале сам себе друг
for i in range(1, n + 1):
    frends[i] = {i}

while k > 0: # Вводим k пар и добавляем в множество друзей для каждого из пары
    temp = list(map(int, input().split()))
    frends[temp[0]].add(temp[1])
    frends[temp[1]].add(temp[0])
    k -= 1

# Для всех друзей ищем людей с таким же множеством друзей и среди них ищем максимально большое количество.
maxteam = []
for frend in frends:
    team = []
    for i in range(1, n + 1):
        if frends[frend].issubset(frends[i]):
            team.append(i)
    if len(team) > len(maxteam):
        maxteam = team
maxteam.sort()
print(len(maxteam))
print(*maxteam)
    • 1

相关问题