Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Алгоритм Куна

Необходимо в двудольном графе найти максимальное паросочетание

Возможна и следующая формулировка:

Необходимо в двудольном графе найти минимальноё рёберное покрытие


Алгоритм Куна основан на методе чередующихся цепей.

Асимптотика O(NM).


Листинг C++

bool dfs_kuhn (int &v, vector < vector < int > > &e, vector < int > &is, vector < int > &p)
{
    if (is[v]) return 0;
    is[v] = 1;
    for (int i = 0; i < e[v].size (); ++ i)
    {
        int u = e[v][i] - is.size ();
        if (p[u] == - 1 || dfs_kuhn (p[u], e, is, p))
        {
            p[u] = v;
            return 1;
        }
    }
    return 0;
}

void kuhn (int n, int m, vector < vector < int > > &e, vector < int > &p)
{
    p.assign (m, - 1);
    for (int i = 0; i < n; ++ i)
    {
        vector < int > is (n, 0);
        dfs_kuhn (i, e, is, p);
    }
}

31.05.2007, 08:10