Algoritmul lui Kuhn (Ungar)

algoritm-kuhn

h1. Algoritmul lui Kuhn (Ungar)

h1. Algoritmul lui Kuhn(Ungar)

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

(Categoria _Algoritmi_, Autor _Tiberiu Florea_)

(Categoria _Algoritmi_, autor _Florea Tiberiu_)

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 (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;
            }

    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 ();
}

        for (j = 1; j <= N; ++ j) scanf("%d", &G[i][j]);
    memset (vr, 0, sizeof (vr)), memset (vc, 0, sizeof (vc));

    memset (l, 0, sizeof (l)), memset (r, 0, sizeof (r));

    memset (1, 0, sizeof (1)), memset (r, 0, sizeof (r));

    for (cnt = 0; cnt < N; ++ cnt) {
        memset (cr, 0, sizeof (cr)), memset (p, 0, sizeof (p));

        memcpy (cc, l, sizeof (cc));

        memcpy (cc, 1, sizeof (cc));

        find_zero ();
    }

3701