Статья Автор: Логинов Даниил
1

def ST_EN(wait):
    sten = {0: (0, 0)}
    while len(sten) <= len(prev):
        for i in prev:
            if any(xd not in sten for xd in prev[i]) or i in sten:
                continue
            st = max([sten[xd][1] for xd in prev[i]]) + wait[i]
            sten[i] = (
                st + 1,
                st + time[i]
            )
    return sten

time = {}
prev = {}
nxt = {0: set()}
wait = {0: 0}
with open("file0.txt") as file:
    for i in file:
        x, y, *z = map(int, i.replace(";", " ").split())
        time[x] = y
        prev[x] = z
        wait[x] = 0
        nxt[x] = set()

for z in prev:
    for iz in prev[z]:
        nxt[iz] |= {z}

"""
def bfs():
    lvls = [{0}]
    visited = set()
    while len(visited) < len(prev):
        lvls.append(set())
        for next in lvls[-2] - visited:
            lvls[-1] |= nxt[next]
        visited |= lvls[-2]
    return [k for i in range(1, len(lvls) - 1) for k in sorted(lvls[i])]
""" #bfs

sten = ST_EN(wait)
order = sorted([k for k in prev], key=lambda a: sten[a][0])

for i in order:
    print(i, sten[i])

def go(mx):
    visited = set()
    t = 1
    result = 0
    ln = 0
    while len(visited) < len(prev):
        cnt = 0
        for j in prev:
            if j in visited:
                continue
            if sten[j][0] <= t - wait[j] <= sten[j][1]:
                cnt += 1
            if t == sten[j][1] + wait[j]:
                visited.add(j)
        if cnt == mx:
            ln += 1
            result = max(result, ln)
        else:
            ln = 0
    return result


def req(x, i = 0):
    #print(wait)
    if i == len(prev):
        return go(x)
    d0 = max([0] + [sten[j][1] + wait[j] - sten[order[i]][0] - 1 for j in prev[order[i]]])
    #print(d0)
    d = set()
    for j in range(i + 1, len(prev)):
        dd = sten[order[j]][1] + wait[order[j]] - sten[order[i]][0] - d0
        if dd > 0:
            d.add(dd)
    result = 0
    for id in d:
        #print(id + d0)
        wait[order[i]] = id + d0
        print(wait)
        result = max(result, req(x, i + 1))
    wait[order[i]] = 0
    return result

print(req(2))
Чтобы оставить комментарий нужна авторизация
Печать