Тема: Задача Корупція

Хто може кинути розв'язок або сказати як зробити дану задачу?
http://acm.timus.ru/problem.aspx?space=1&num=1198

2 Востаннє редагувалося 0x9111A (06.12.2016 21:02:39)

Re: Задача Корупція

Для кожного сенатора визначіть список сенаторві на яких він має вплив (як прямо так і не прямо через тих на яких прямо), і ті сенатори в яких цей список включатиме всіх - наймогутніші

П.С. Якщо не секрет, нащо вам то?

Подякували: BronzChef20561

3

Re: Задача Корупція

Дякую, та просто так вирішив зробити)))

4

Re: Задача Корупція

Просто будуєте зв'язаний граф для кожного сенатора.
  .

Подякували: #Sparta, BronzChef20562

5

Re: Задача Корупція

Якраз розглядали дану задачу на факультативі і пан koala все вірно підказав.

Подякували: BronzChef20561

6

Re: Задача Корупція

#Sparta написав:

Якраз розглядали дану задачу на факультативі і пан koala все вірно підказав.

а є код з факультативу?)

7

Re: Задача Корупція

Хапайте Python:

n = int(input())
data = [set()]+[set(int(x) for x in input().split()) for _ in range(n)]

print(data)

def infl(num,data,visited):
    visited.add(num)
    res = data[num].copy()
    for x in data[num]:
        if x not in visited:
            res |= infl(x,data,visited)
    data[num] = res
    return data[num]

for x in range(len(data)):
    infl(x,data,set())

print([x for x in range(n) if len(data[x])>n])

Вдався до маленьких хитрощів - наприклад, додав віртуального "сенатора №0", щоб не змінювати номери в масиві.

Подякували: BronzChef2056, #Sparta2

8

Re: Задача Корупція

Ефективніша ідея: робимо матрицю суміжності (можна бітову) і в циклі по рядках робимо АБО з тими рядками, з якими у відповідних клітинках стоять одиниці, доки не буде n проходів без змін.