Cod sursa(job #294194)

Utilizator raula_sanChis Raoul raula_san Data 2 aprilie 2009 13:07:47
Problema Flux maxim de cost minim Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 5.01 kb
#include <stdio.h>

#define MAX_N 351
#define inf 0x3f3f3f3f

int N, M, S, D, Sum, Drum, B;
int F[MAX_N][MAX_N], Cap[MAX_N][MAX_N], Cost[MAX_N][MAX_N], Dist[MAX_N], U[MAX_N], H[MAX_N], P[MAX_N], T[MAX_N];

long long R;

struct nod
{
       int v;
       nod *next;

} *L[MAX_N], *Q, *Qf;

void Add(nod *&l, int v)
{
     nod *p = new nod;
     p->v = v;
     p->next = l;
     l = p;
}
/*
void BellmanFord()
{
     Q = new nod;
     Q->v = S;
     Q->next = NULL;
     Qf = Q;
     U[S] = 1;
     
     int i;
     for ( i = 1; i <= N; ++i ) Dist[i] = inf;
     Dist[S] = 0;
     
     while(Q)
     {
             int x = Q->v;
             nod *p;
             
             for ( p = L[x]; p; p = p->next )
                 if(Cap[x][p->v]-F[x][p->v] > 0 && Dist[x]+Cost[x][p->v] < Dist[p->v])
                 {
                     Dist[p->v] = Dist[x] + Cost[x][p->v];
                     
                     if(!U[p->v])
                     {
                                 nod *q = new nod;
                                 q->v = p->v;
                                 q->next = NULL;
                                 Qf->next = q;
                                 Qf = q;
                                 
                                 U[p->v] = 1;
                     }
                 }
                 
             U[x] = 0;
             p = Q;
             Q = Q->next;
             delete p;
     }
     
     Sum = Dist[D];
}
*/
void Push(int k)
{
     while(k > 1)
     {
             int t = k >> 1;
     
             if(Dist[H[t]] > Dist[H[k]])
             {
                   P[H[t]] = k;
                   P[H[k]] = t;
                   
                   H[t] ^= H[k] ^= H[t] ^= H[k];
                   k = t;
             }
             else
                 k = 1;
     }
}

void Pop(int r, int b)
{
     if(r << 1 <= b)
     {
          int st = Dist[H[r<<1]];
          int dr, x = r << 1;
          
          if((r<<1) + 1 <= b) dr = Dist[H[(r<<1)+1]];
          else
              dr = st + 1;
              
          if(st > dr) ++ x;
          
          if(Dist[H[x]] < Dist[H[r]])
          {
                        P[H[x]] = r;
                        P[H[r]] = x;
                        
                        H[x] ^= H[r] ^= H[x] ^= H[r];
                        
                        Pop(x, b);
          }
     }
}

int Min(int i, int j)
{
    return
          i < j ? i : j;
}

long long Dijkstra()
{
     int i; nod *p;
     
     for ( i = 1; i <= N; ++i )
         for ( p = L[i]; p; p = p->next )
             if(Dist[i] != inf && Dist[p->v] != inf) Cost[i][p->v] += Dist[i] - Dist[p->v];
     
     for ( i = 1; i <= N; ++i )
     {
         Dist[i] = inf;
         H[i] = i;
         P[i] = i;
         T[i] = -1;
     }
	 Dist[S] = 0;

     H[1] = S; H[S] = 1;
     P[S] = 1; P[1] = S;
	 B = N;

     while(B > 1 && Dist[H[1]] != inf)
     {
             int nd = H[1];
             
             for ( p = L[nd]; p; p = p->next )
                 if(Cap[nd][p->v]-F[nd][p->v] > 0 && Dist[nd]+Cost[nd][p->v] < Dist[p->v])
                 {
                     Dist[p->v] = Dist[nd] + Cost[nd][p->v];
                     T[p->v] = nd;
                     Push(P[p->v]);
                 }
                 
             H[1] = H[B--];
             P[H[1]] = 1;
             Pop(1, B);
     }

     if(Dist[D] != inf)
     {
                Drum = 1;
                
                int r = inf;
                for ( i = D; i != S; i = T[i] ) r = Min(r, Cap[T[i]][i]-F[T[i]][i]);
                for ( i = D; i != S; i = T[i] )
                {
                    F[T[i]][i] += r;
                    F[i][T[i]] -= r;
                }
                
                Sum += Dist[D];
                return Sum * r;
     }
     
     return 0;
}

long long Flux()
{
     Drum = 1;
     
     while(Drum)
     {
                Drum = 0;
                R += Dijkstra();
     }
     
     return R;
}

int BellmanFord()
{
	int i, stop = 0, j, k;

	for (i = 1; i <= N; i++) Dist[i] = inf;
	Dist[S] = 0;

	for (i = 1; i <= N && !stop; i++)
	{
		stop = 1;
        nod *p;

		for (j = 1; j <= N; j++)
			for (p=L[j]; p; p=p->next)
				if (Cap[j][p->v]-F[j][p->v]>0 && Dist[j]+Cost[j][p->v]<Dist[p->v])
				{
					stop = 0;
					Dist[p->v] = Dist[j] + Cost[j][p->v];
				}
	}

	Sum = Dist[D];

	return stop;
}

int main()
{
    freopen("fmcm.in", "rt", stdin);
    freopen("fmcm.out", "wt", stdout);
    
    scanf("%d %d %d %d", &N, &M, &S, &D);

    int i, x, y, cap, z;
    
    for ( i = 1; i <= M; ++i )
    {
        scanf("%d %d %d %d", &x, &y, &cap, &z);
        
        Cap[x][y] = cap;
        Cost[x][y] = z;
        Cost[y][x] = -z;
        
        Add(L[x], y);
        Add(L[y], x);
    }

    BellmanFord();

    printf("%lld\n", Flux());
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}