На головну

Алгоритм Куна знаходження найбільшого паросполучення в дводольному графі

  1. II. Правила орфографії, пов'язані з фонемно-графемно
  2. алгоритм
  3. алгоритм
  4. Алгоритм 4.2. Ліва факторізація граматики
  5. Алгоритм 5.2. Побудова табліці предиктивного АНАЛІЗУ

Дан двочастковий граф  , що містить  вершин і  ребер. Потрібно знайти найбільше паросполучення, тобто вибрати якомога більше ребер, щоб жодне вбрання ребро не мало загальної вершини ні з яким іншим обраним ребром.

теорема Бержа

Формулювання. Паросочетание є максимальним тоді і тільки тоді, коли не існує збільшують щодо нього ланцюгів.

int n, k;

vector > g;

vector mt;

vector used;

bool try_kuhn (int v) {

if (used [v]) return false;

used [v] = true;

for (size_t i = 0; i

int to = g [v] [i];

if (mt [to] == -1 || try_kuhn (mt [to])) {

mt [to] = v;

return true;

}

}

return false;

}

int main () {

... Читання графа ...

mt.assign (k, -1);

vector used1 (n);

for (int i = 0; i

for (size_t j = 0; j

if (mt [g [i] [j]] == -1) {

mt [g [i] [j]] = i;

used1 [i] = true;

break;

}

for (int i = 0; i

if (used1 [i]) continue;

used.assign (n, false);

try_kuhn (i);

}

for (int i = 0; i

if (mt [i]! = -1)

printf ( "% d% d \ n", mt [i] +1, i + 1);

}

12) Ейлер

int phi (int n) {

int result = n;

for (int i = 2; i * i <= n; ++ i)

if (n% i == 0) {

while (n% i == 0)

n / = i;

result - = result / i;

}

if (n> 1)

result - = result / n;

return result;

}

Binpow

int binpow (int a, int n) {

int res = 1;

while (n) {

if (n & 1)

res * = a;

a * = a;

n >> = 1;

}

return res;

}

 



Пошук точок зчленування | Розширений Евклід

Флойд-Уоршелл | Алгоритм пошуку компонент зв'язності в графі | дискретного логарифмування | Теорема Піка. | Z-функція рядка і її обчислення | Знаходження наідліннейшей зростаючої підпослідовності | Знаходження найбільшою нульовий подматріци | Біноміальні коефіцієнти | числа Каталана | намиста |

© um.co.ua - учбові матеріали та реферати