algoritm-kuhn

 Algoritmul lui Kuhn (Ungar)

h1. Algoritmul lui Kuhn(Ungar)

h1. Algoritmul lui Kuhn (Ungar)

== include(page="template/implica-te/scrie-articole" user_id="sims_gl") ==

(Categoria _Algoritmi_, autor _Florea Tiberiu_)

(Categoria _Algoritmi_, Autor _Tiberiu Florea_)

h2. Introducere

    for (i = 1; i <= N; ++ i) if (cr[i]) vr[i] += min;
    for (j = 1; j <= N; ++ j) if (!cc[j]) vc[j] += min;

    for (j = 1; j <= N; ++ j) if (!cc[j] && G[i][j] + vr[i] == vc[j])
        if (r[i]) {
            p[i] = j, cr[i] = 1, cc[r[i]] = 0;
            break;
        } else {
            do t = l[j], r[i] = j, l[j] = i, i = t, j = p[i]; while (t);
            return;
        }

    for (i = 1; i <= N; ++ i) if (!cr[i])
        for (j = 1; j <= N; ++ j) if (!cc[j] && G[i][j] + vr[i] == vc[j])
            if (r[i]) {
                p[i] = j, cr[i] = 1, cc[r[i]] = 0;
                break;
            } else {
                do t = l[j], r[i] = j, l[j] = i, i = t, j = p[i]; while (t);
                return;
            }

    find_zero ();
}

3701