• Russian
    • Начало » Разборы » Analysis list for problem "Паросочетание"
    Menu
    1. Analysis list
    2. Список задач
    3. Задачи с разбором
    Категории
    FAQ(12)
    IT(0)
    Qwerty(0)
    Алгоритмы(60)
    Длинная Арифметика(0)
    Олимпиады(0)
    Языки программирования(0)
    Сортировать по: Последние По голосам Просмотры

    Список разборов

    Голосов
    1
    Comments
    0
    Просмотров
    37

    Теория графов → Разбор Паросочетание 2

    если добавить исток и сток, ориентировать ребра, то можно найти макс. поток методом Эдмондса Карпа.

    Все это займет O(N * M * M) или же по другому O(FM), где F величина потока

    edmonds karp maxflow
    Дата:

    2010 Август 30


    Автор: serekovabzal

    CR: 85.357 AR: 11.000

    Голосов
    1
    Comments
    0
    Просмотров
    57

    Теория графов → Разбор Паросочетание

    Воспользуемся стандартным алгоритмом Куна. Описание его работы и реализацию можно найти на emaxx например. http://e-maxx.ru/algo/kuhn_matching

    Дата:

    2010 Март 17


    Автор: ZoRGaN

    CR: 185.332 AR: 29.000


    Analysis tags
    a*b%c analysis arithmetics a^b%c backtracking bfs circles combinatorics dynamic edmonds euclid fast powering formula fraction fractions geometry induction karp line-intersection linear-equations log maxflow neerc.ifmo.ru olympiads.ru pascal-triangle power programming recursion root rsq sequence simple math sqrt stl string геометрия Двоичное Дейкстра динамика евклид задачи на реализацию К числа капрекар линейные-уравнения логика перебор пересечение линий разбор сравнение структуры данных число
    register
    логин
    forgot password?
    resend validation
    соревнования
    current contests
    future contests
    past contests
    problem archives
    статьи
    write an article
    category tree for articles
    article archive
    задачи
    problems with analysis
    category tree for problems
    Разборы
    question-answer
    ask question
    пользователи
    top coders
    top authors
    события
    event calendar
    будущие события
    event archive
    algoprog NEWS

    Powered by django, eJudge.