Cod sursa(job #5149)

Utilizator vlad_popaVlad Popa vlad_popa Data 10 ianuarie 2007 20:03:12
Problema Cc Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>

#define FIN "cc.in"
#define FOUT "cc.out"
#define nmax 101

int a[nmax][nmax], d[nmax], v[nmax], s, k, n,
          i, j, i0, li0, c0, R, u, j0, u0, c;

void calcul ()
{
  d[1] = 1;
  v[1] = 1;
  s = a[1][1];
  for (k = 2; k <= n; k++)
   {
     li0 = a[1][k] + a[k][d[1]] - a[1][d[1]];
     i0 = 1;
     c0 = d[i0];
     j = d[i0];
     for (i = 1; i < k; i++)
      {
        j = d[i];
        R = a[i][k] + a[k][j] - a[i][j];
        if (R < li0)
         {
           li0 = R;
           i0 = i;
           j = d[i];
           c0 = j;
           j0 = j;
         }
        for (c = 1; c < k; c++)
          if (c - j)
           {
             u = v[c];
             R = a[i][k] + a[k][c] - a[i][j] - a[u][c] + a[u][j];
             if (R < li0)
              {
                li0 = R;
                c0 = c;
                i0 = i;
                u0 = u;
                j0 = j;
              }
           }
      }
     if (li0 >= a[k][k])
      {
        s += a[k][k];
        d[k] = k;
        v[k] = k;
      }
     else
      {
        s += li0;
        if (c0 == j0)
         {
           d[i0] = k;
           d[k] = c0;
           v[c0] = i0;
           v[k] = i0;
         }
        else
         {
           d[i0] = k;
           v[k] = i0;
           d[u0] = j0;
           v[j0] = u0;
           d[k] = c0;
           v[c0] = k;
         }
      }
   }
}

int
 main ()
{
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt", stdout);

  scanf ("%d", &n);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      scanf ("%d", &a[i][j]);
  calcul();
  printf ("%d\n", s);
  return 0;
}