/*  -- translated by f2c (version 20010320).
   You must link the resulting object file with the libraries:
-lf2c -lm   (in that order)
*/

#include "f2c.h"

/* Subroutine */ int assct_(n, a, c__, t)
integer *n, *a, *c__, *t;
{
    /* System generated locals */
    integer i__1, i__2;
    static integer equiv_0[131], equiv_1[130];

    /* Local variables */
    static integer kslc, kslr, h__, i__, j, k, l, m, q, r__, s, u[131];
#define ch (equiv_1)
    static integer lc[130], lj, lm;
#define rh (equiv_0)
    static integer nl, nm, lr[130];
#define lz (equiv_0)
#define nz (equiv_1)
    static integer maxnum, np1, slc[130], slr[130];


/* THIS SUBROUTINE SOLVES THE SQUARE ASSIGNMENT PROBLEM */
/* THE MEANING OF THE INPUT PARAMETERS IS */
/* N = NUMBER OF ROWS AND COLUMNS OF THE COST MATRIX, WITH */
/*     THE CURRENT DIMENSIONS THE MAXIMUM VALUE OF N IS 130 */
/* A(I,J) = ELEMENT IN ROW I AND COLUMN J OF THE COST MATRIX */
/* ( AT THE END OF COMPUTATION THE ELEMENTS OF A ARE CHANGED) */
/* THE MEANING OF THE OUTPUT PARAMETERS IS */
/* C(J) = ROW ASSIGNED TO COLUMN J (J=1,N) */
/* T = COST OF THE OPTIMAL ASSIGNMENT */
/* ALL PARAMETERS ARE INTEGER */
/* THE MEANING OF THE LOCAL VARIABLES IS */
/* A(I,J) = ELEMENT OF THE COST MATRIX IF A(I,J) IS POSITIVE, */
/*          COLUMN OF THE UNASSIGNED ZERO FOLLOWING IN ROW I */
/*          (I=1,N) THE UNASSIGNED ZERO OF COLUMN J (J=1,N) */
/*          IF A(I,J) IS NOT POSITIVE */
/* A(I,N+1) = COLUMN OF THE FIRST UNASSIGNED ZERO OF ROW I */
/*            (I=1,N) */
/* CH(I) = COLUMN OF THE NEXT UNEXPLORED AND UNASSIGNED ZERO */
/*         OF ROW I (I=1,N) */
/* LC(J) = LABEL OF COLUMN J (J=1,N) */
/* LR(I) = LABEL OF ROW I (I=1,N) */
/* LZ(I) = COLUMN OF THE LAST UNASSIGNED ZERO OF ROW I(I=1,N) */
/* NZ(I) = COLUMN OF THE NEXT UNASSIGNED ZERO OF ROW I(I=1,N) */
/* RH(I) = UNEXPLORED ROW FOLLOWING THE UNEXPLORED ROW I */
/*         (I=1,N) */
/* RH(N+1) = FIRST UNEXPLORED ROW */
/* SLC(K) = K-TH ELEMENT CONTAINED IN THE SET OF THE LABELLED */
/*          COLUMNS */
/* SLR(K) = K-TH ELEMENT CONTAINED IN THE SET OF THE LABELLED */
/*          ROWS */
/* U(I) = UNASSIGNED ROW FOLLOWING THE UNASSIGNED ROW I */
/*        (I=1,N) */
/* U(N+1) = FIRST UNASSIGNED ROW */

/* THE VECTORS C,CH,LC,LR,LZ,NZ,SLC,SLR MUST BE DIMENSIONED */
/* AT LEAST AT (N), THE VECTORS RH,U AT  LEAST AT (N+1), */
/* THE MATRIX A AT LEAST AT (N,N+1) */

/* INITIALIZATION */
    /* Parameter adjustments */
    --c__;
    a -= 131;

    /* Function Body */
    maxnum = 100000000;
    np1 = *n + 1;
    i__1 = *n;
    for (j = 1; j <= i__1; ++j) {
c__[j] = 0;
lz[j - 1] = 0;
nz[j - 1] = 0;
u[j - 1] = 0;
/* L10: */
    }
    u[np1 - 1] = 0;
    *t = 0;
/* REDUCTION OF THE INITIAL COST MATRIX */
    i__1 = *n;
    for (j = 1; j <= i__1; ++j) {
s = a[j * 130 + 1];
i__2 = *n;
for (l = 2; l <= i__2; ++l) {
    if (a[l + j * 130] < s) {
s = a[l + j * 130];
    }
/* L20: */
}
*t += s;
i__2 = *n;
for (i__ = 1; i__ <= i__2; ++i__) {
    a[i__ + j * 130] -= s;
/* L30: */
}
/* L40: */
    }
    i__1 = *n;
    for (i__ = 1; i__ <= i__1; ++i__) {
q = a[i__ + 130];
i__2 = *n;
for (l = 2; l <= i__2; ++l) {
    if (a[i__ + l * 130] < q) {
q = a[i__ + l * 130];
    }
/* L50: */
}
*t += q;
l = np1;
i__2 = *n;
for (j = 1; j <= i__2; ++j) {
    a[i__ + j * 130] -= q;
    if (a[i__ + j * 130] != 0) {
goto L60;
    }
    a[i__ + l * 130] = -j;
    l = j;
L60:
    ;
}
/* L70: */
    }
/* CHOICE OF THE INITIAL SOLUTION */
    k = np1;
    i__1 = *n;
    for (i__ = 1; i__ <= i__1; ++i__) {
lj = np1;
j = -a[i__ + np1 * 130];
L80:
if (c__[j] == 0) {
    goto L130;
}
lj = j;
j = -a[i__ + j * 130];
if (j != 0) {
    goto L80;
}
lj = np1;
j = -a[i__ + np1 * 130];
L90:
r__ = c__[j];
lm = lz[r__ - 1];
m = nz[r__ - 1];
L100:
if (m == 0) {
    goto L110;
}
if (c__[m] == 0) {
    goto L120;
}
lm = m;
m = -a[r__ + m * 130];
goto L100;
L110:
lj = j;
j = -a[i__ + j * 130];
if (j != 0) {
    goto L90;
}
u[k - 1] = i__;
k = i__;
goto L140;
L120:
nz[r__ - 1] = -a[r__ + m * 130];
lz[r__ - 1] = j;
a[r__ + lm * 130] = -j;
a[r__ + j * 130] = a[r__ + m * 130];
a[r__ + m * 130] = 0;
c__[m] = r__;
L130:
c__[j] = i__;
a[i__ + lj * 130] = a[i__ + j * 130];
nz[i__ - 1] = -a[i__ + j * 130];
lz[i__ - 1] = lj;
a[i__ + j * 130] = 0;
L140:
;
    }
/* RESEARCH OF A NEW ASSIGNMENT */
L150:
    if (u[np1 - 1] == 0) {
return 0;
    }
    i__1 = *n;
    for (i__ = 1; i__ <= i__1; ++i__) {
ch[i__ - 1] = 0;
lc[i__ - 1] = 0;
lr[i__ - 1] = 0;
rh[i__ - 1] = 0;
/* L160: */
    }
    rh[np1 - 1] = -1;
    kslc = 0;
    kslr = 1;
    r__ = u[np1 - 1];
    lr[r__ - 1] = -1;
    slr[0] = r__;
    if (a[r__ + np1 * 130] == 0) {
goto L220;
    }
L170:
    l = -a[r__ + np1 * 130];
    if (a[r__ + l * 130] == 0) {
goto L180;
    }
    if (rh[r__ - 1] != 0) {
goto L180;
    }
    rh[r__ - 1] = rh[np1 - 1];
    ch[r__ - 1] = -a[r__ + l * 130];
    rh[np1 - 1] = r__;
L180:
    if (lc[l - 1] == 0) {
goto L200;
    }
    if (rh[r__ - 1] == 0) {
goto L210;
    }
L190:
    l = ch[r__ - 1];
    ch[r__ - 1] = -a[r__ + l * 130];
    if (a[r__ + l * 130] != 0) {
goto L180;
    }
    rh[np1 - 1] = rh[r__ - 1];
    rh[r__ - 1] = 0;
    goto L180;
L200:
    lc[l - 1] = r__;
    if (c__[l] == 0) {
goto L360;
    }
    ++kslc;
    slc[kslc - 1] = l;
    r__ = c__[l];
    lr[r__ - 1] = l;
    ++kslr;
    slr[kslr - 1] = r__;
    if (a[r__ + np1 * 130] != 0) {
goto L170;
    }
L210:
    if (rh[np1 - 1] > 0) {
goto L350;
    }
/* REDUCTION OF THE CURRENT COST MATRIX */
L220:
    h__ = maxnum;
    i__1 = *n;
    for (j = 1; j <= i__1; ++j) {
if (lc[j - 1] != 0) {
    goto L240;
}
i__2 = kslr;
for (k = 1; k <= i__2; ++k) {
    i__ = slr[k - 1];
    if (a[i__ + j * 130] < h__) {
h__ = a[i__ + j * 130];
    }
/* L230: */
}
L240:
;
    }
    *t += h__;
    i__1 = *n;
    for (j = 1; j <= i__1; ++j) {
if (lc[j - 1] != 0) {
    goto L290;
}
i__2 = kslr;
for (k = 1; k <= i__2; ++k) {
    i__ = slr[k - 1];
    a[i__ + j * 130] -= h__;
    if (a[i__ + j * 130] != 0) {
goto L280;
    }
    if (rh[i__ - 1] != 0) {
goto L250;
    }
    rh[i__ - 1] = rh[np1 - 1];
    ch[i__ - 1] = j;
    rh[np1 - 1] = i__;
L250:
    l = np1;
L260:
    nl = -a[i__ + l * 130];
    if (nl == 0) {
goto L270;
    }
    l = nl;
    goto L260;
L270:
    a[i__ + l * 130] = -j;
L280:
    ;
}
L290:
;
    }
    if (kslc == 0) {
goto L350;
    }
    i__1 = *n;
    for (i__ = 1; i__ <= i__1; ++i__) {
if (lr[i__ - 1] != 0) {
    goto L340;
}
i__2 = kslc;
for (k = 1; k <= i__2; ++k) {
    j = slc[k - 1];
    if (a[i__ + j * 130] > 0) {
goto L320;
    }
    l = np1;
L300:
    nl = -a[i__ + l * 130];
    if (nl == j) {
goto L310;
    }
    l = nl;
    goto L300;
L310:
    a[i__ + l * 130] = a[i__ + j * 130];
    a[i__ + j * 130] = h__;
    goto L330;
L320:
    a[i__ + j * 130] += h__;
L330:
    ;
}
L340:
;
    }
L350:
    r__ = rh[np1 - 1];
    goto L190;
/* ASSIGNMENT OF A NEW ROW */
L360:
    c__[l] = r__;
    m = np1;
L370:
    nm = -a[r__ + m * 130];
    if (nm == l) {
goto L380;
    }
    m = nm;
    goto L370;
L380:
    a[r__ + m * 130] = a[r__ + l * 130];
    a[r__ + l * 130] = 0;
    if (lr[r__ - 1] < 0) {
goto L390;
    }
    l = lr[r__ - 1];
    a[r__ + l * 130] = a[r__ + np1 * 130];
    a[r__ + np1 * 130] = -l;
    r__ = lc[l - 1];
    goto L360;
L390:
    u[np1 - 1] = u[r__ - 1];
    u[r__ - 1] = 0;
    goto L150;
} /* assct_ */

#undef nz
#undef lz
#undef rh
#undef ch


#ifdef uNdEfInEd
comments from the converter:  (stderr from f2c)
   assct:
#endif