Cod sursa(job #135820)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 14 februarie 2008 17:18:21
Problema Paznici2 Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 3.79 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 404
#define QMAX ((1<<18)-1)
#define INF 666000666

int N, M, C[NMAX][NMAX], F[NMAX][NMAX], Flow, Cmin;
int tata[NMAX], cup[NMAX], tip[NMAX], D[NMAX], inQ[NMAX], Q[QMAX+10];
int Ok[NMAX][NMAX];
int op;

void read()
{
     int i, j;

     freopen("paznici2.in", "r", stdin);
     scanf("%d", &N);

     for (i = 0; i < NMAX; i++)
         for (j = 0; j < NMAX; j++) C[i][j] = INF;

     for (i = 1; i <= N; i++)
     {
         for (j = 1; j <= N; j++)
             scanf("%d", &C[i][N+j]), C[N+j][i] = C[i][N+j];
     }

 }

void flow(int s)
{
        int i, j, lo, hi, min;

        for (i = 0; i < NMAX; i++) D[i] = INF, tata[i] = inQ[i] = tip[i] = 0;

        Q[0] = s;
        D[s] = 0;
        inQ[s] = 1;

        for (lo = 0, hi = 1; lo != hi; lo = (lo+1)&QMAX)
        {
                i = Q[lo];

                if (i<=N)
                {
                
                for (j = N+1; j <= M; j++)
                  if (C[i][j]>=0)
                    if ((F[i][j]<1)&&(D[j]>(D[i]+C[i][j])))
                    {
                        D[j] = D[i]+C[i][j];
                        tata[j] = i;
                        if (!inQ[j]) inQ[j] = 1, Q[hi] = j, hi = (hi+1)&QMAX;
                    }
                }
                else
                {

                j = cup[i];
                if (j>0)
                    {
                        if ((F[i][j]<0)&&(D[j]>(D[i]-C[i][j])))
                        {
                            D[j] = D[i]-C[i][j];
                            tata[j] = i;
                            if (!inQ[j]) inQ[j] = 1, Q[hi] = j, hi = (hi+1)&QMAX;
                        }
                    }
                }

                inQ[i] = 0;
        }

        min = INF;

        for (j = N+1; j <= M; j++)
            if (!cup[j]&&min>D[j]) min = D[j], i = j;

        Cmin += min;
        Flow++;

        for (; i>0; i = tata[i])
            F[tata[i]][i]++, F[i][tata[i]]--;

        for (i = 1; i <= N; i++)
            for (j = N+1; j <= M; j++)
                if (F[i][j]==1) cup[j] = i;
}

void solve()
{
        int i, j, k, cok, old, cc[NMAX], t1, t2;

        for (i = 1, M = 2*N; i <= N; i++) flow(i);

        cok = Cmin;

        for (i = N+1; i <= M; i++) Ok[i-N][cup[i]] = 1;

        if (N<81) {

        for (i = 1; i <= N; i++)
        {
            for (k = 1; k <= N; k++) cc[k] = C[i][N+k], C[N+k][i] = C[i][N+k] = INF;

            for (k = 1; k <= N; k++)
            {
                C[i][k+N-1] = C[k+N-1][i] = INF;
                C[i][k+N] = C[N+k][i] = cc[k];

                memset(F,0,sizeof(F));
                memset(cup,0,sizeof(cup));

                Flow = 0, Cmin = 0;
                for (j = 1; j <= N; j++) {
                    flow(j);
                    if (Cmin>cok) { Cmin = -1; break; }
                   }
               if (Cmin==cok&&Flow==N)
                    for (j = N+1; j <= M; j++) Ok[ j-N ][ cup[j] ] = 1;
            }
            for (j = 1; j <= N; j++) C[ j+N ][i] = C[i][ j+N ] = cc[j];
        }

        }

       else
        {
            for (i = N+1; i <= M; i++)
                for (j = N+1; j <= M; j++)
                    if (C[cup[i]][i]==C[cup[i]][j])
                        Ok[cup[i]][j-N] = 1;
        }

        Cmin = cok;
}

void write()
{
    int i, j, nr;

    freopen("paznici2.out", "w", stdout);

    printf("%d\n", Cmin);

    for (i = 1; i <= N; i++)
    {
        for (j = 1, nr = 0; j <= N; j++) nr += Ok[i][j];
        printf("%d ", nr);
        for (j = 1; j <= N; j++)
            if (Ok[i][j]) printf("%d ", j);
        printf("\n");
    }
}

int main()
{
    read();
    solve();
    write();
    return 0;
}