Cod sursa(job #135803)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 14 februarie 2008 16:32:43
Problema Paznici2 Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 4.49 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], type[NMAX], D[NMAX], InQ[NMAX], Q[QMAX+10];
int Ok[NMAX][NMAX];
int op;

void read()
{
     int i, j;

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

     for (i = 0; i < N; i++)
         for (j = 0; j < N; 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];
     }

     for (i = 1; i <= N; i++) C[0][i] = C[i][0] = 0;
     for (i = N+1; i <= 2*N; i++) C[i][2*N+1] = C[2*N+1][i] = 0;
 }


void flow(int sursa)
{
        int p1 = 0, p2 = 1, i, j, nod, tata[NMAX], tip[NMAX], min;

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

        Q[p1] = sursa;
        D[ sursa ] = 0;
        InQ[ sursa ] = 1;

        for (p1 = 0, p2 = 1; p1 != p2; p1 = (p1+1)&QMAX)
        {
                nod = Q[p1];
                
                if (nod <= N)
                {
                   for (i = N+1; i <= M; i++)
                       if (!F[nod][i] && D[i] > D[nod]+C[nod][i])
                       {
                                D[i] = D[nod]+C[nod][i];
                                tata[i] = nod;
                                if (!InQ[i])
                                {
                                        InQ[i] = 1;
                                        Q[p2] = i;
                                        p2 = (p2+1)&(QMAX-1);
                                }
                       }
                }
                else
                {
                        if (cup[nod] > 0 && (D[cup[nod]] > D[nod]-C[cup[nod]][nod]))
                        {
                                D[cup[nod]] = D[nod]-C[cup[nod]][nod];
                                tata[cup[nod]] = nod;
                                tip[cup[nod]] = 1;
                                if (!InQ[cup[nod]])
                                {
                                        InQ[cup[nod]] = 1;
                                        Q[p2] = cup[nod];
                                        p2 = (p2+1)&(QMAX-1);
                                }
                        }
                }
                InQ[nod] = 0;
        }

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

        Cmin += min;
        Flow++;

        for (; j; j = tata[j])
        {
                if (!tip[j])
                {
                        F[tata[j]][j]++;
                        cup[j] = tata[j];
                }
                else
                    F[j][tata[j]]--;
        }
        
}

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[cup[i]][i-N] = 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[ cup[j] ][j-N] = 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("paznici.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;
}