Cod sursa(job #46890)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 3 aprilie 2007 10:22:25
Problema Traseu Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <stdio.h>
#define NMAX 66
#define INF 666000666

int N, M, A[NMAX][NMAX], C[NMAX][NMAX], D[NMAX][NMAX], Dist[NMAX];
int F[NMAX][NMAX], Cap[NMAX][NMAX];
int Q[NMAX*NMAX*NMAX], inQ[NMAX], Gi[NMAX], Go[NMAX];
int T[NMAX], Sol, Cup[NMAX];

int eflux(int sursa)
{
        int i, j, tata[NMAX], cup[NMAX], tip[NMAX], lo, hi, min, p;

        for (i = 0; i < NMAX; i++) Dist[i] = INF, tata[i] = -1, cup[i] = 0, tip[i] = 0;

        Dist[sursa] = 0; Q[0] = sursa; inQ[sursa] = 1; cup[sursa] = -1;

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

			   for (j = 1; j <= N+1; j++)
                   if ((F[i][j] < Cap[i][j]) && (Dist[j] > Dist[i]+D[i][j]))
                   {
                            Dist[j] = Dist[i]+D[i][j];
                            tata[j] = i;
                            if (!inQ[j]) Q[hi++] = j, inQ[j] = 1;
                   }
               if ( (cup[i] > 0) && (Dist[cup[i]] > Dist[i]-D[cup[i]][i]) )
               {
                  Dist[cup[i]] = Dist[i]-D[cup[i]][i];
                  tata[cup[i]] = i; tip[cup[i]] = 1;
                  if (!inQ[cup[i]]) Q[hi++] = cup[i], inQ[cup[i]] = 1;
               }
			   inQ[i] = 0;
        }


		min = 8;

		if (Dist[N+1] == INF) return 0;

		min = INF; 
        for (i = N+1; i > 0; i = tata[i])
            if (tip[i] == 0)
            {
				if (Cap[tata[i]][i] - F[tata[i]][i] < min)
					min = Cap[tata[i]][i] - F[tata[i]][i];
			}
			else
				if (F[i][tata[i]] < min)
					min = F[i][tata[i]];
		

        for (i = N+1; i > 0; i = tata[i])
            if (tip[i] == 0)
            {
                F[tata[i]][i] += min;
                Sol += (D[tata[i]][i]*min);
                cup[i] = tata[i];
            }
            else F[i][tata[i]]-= min;
        return 1;
}

int main()
{
        int i, j, c, num = 0, num2 = 0, k;

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

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

        while (M--)
        {
                scanf("%d %d %d", &i, &j, &c);
                A[i][j] = 1; C[i][j] = c; D[i][j] = c; Cap[i][j] = INF;
                Gi[j]++; Go[i]++;
                Sol += c;
        }

        for (i = 1; i <= N; i++)
            if (Gi[i]<Go[i]) A[i][N+1] = 1, Cap[i][N+1] = Go[i]-Gi[i], D[i][N+1] = 0;
            else
                if (Gi[i]>Go[i]) A[0][i] = 1, Cap[0][i] = Gi[i]-Go[i], D[0][i] = 0;

        for (k = 1; k <= N; k++)
            for (i = 1; i <= N; i++)
                for (j = 1; j <= N; j++)
                    //if (A[i][k]+A[k][j] == 2)
                       if (D[i][j] > D[i][k]+D[k][j])
                          D[i][j] = D[i][k]+D[k][j], Cap[i][j] = INF;



        for (j = 1; j == 1;) j = eflux(0);

        freopen("traseu.out", "w", stdout);
        printf("%d\n", Sol);

        return 0;
        
}