Cod sursa(job #781993)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 25 august 2012 16:10:50
Problema Flux maxim de cost minim Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include<fstream>
#include<cstring>
#define inf 1000000000
using namespace std;
typedef struct celula{
        int nod;
        celula *next;
        }*lista;
lista graf[355],v,f;
int i,j,n,m,s,d,tata[355],dist[355],cost[355][355],cap[355][355],sol;
bool ok=true;

inline void update(){
       int nod=d,min=1000000;
        while (tata[nod]!=nod){
          if (cap[tata[nod]][nod]<min) min=cap[tata[nod]][nod];
              nod=tata[nod];
           }
        nod=d;
        while (tata[nod]!=nod){
            sol+=min*cost[tata[nod]][nod];
            cap[tata[nod]][nod]-=min;
            cap[nod][tata[nod]]+=min;
            nod=tata[nod];
           }
}

inline void ford(){
       for (i=1; i<=n; ++i) dist[i]=inf; dist[s]=0; tata[s]=s;
       v=new celula; v->nod=s; v->next=0; f=v; bool ok1=true;
       while (v!=0&&ok1==true) {
             ok1=false;
             for (lista p=graf[v->nod];p; p=p->next)
              if ( cap[v->nod][p->nod]>0&&dist[v->nod]+cost[v->nod][p->nod]<dist[p->nod] ){
                   dist[p->nod]=dist[v->nod]+cost[v->nod][p->nod];
                   lista aux=new celula; aux->nod=p->nod; aux->next=0; f->next=aux; f=aux;
                   tata[p->nod]=v->nod; ok1=true;
                  }
         v=v->next;
        }
       if (dist[d]==inf) ok=false;
}

int main(void){
    ifstream fin("fmcm.in");
    ofstream fout("fmcm.out");
    fin>>n>>m>>s>>d; int x,y,c,z;
    for (i=1; i<=m; ++i){
        fin>>x>>y>>c>>z; cap[x][y]=c; cost[x][y]=z; cost[y][x]=-z;
        v=new celula; v->nod=y; v->next=graf[x]; graf[x]=v;
        v=new celula; v->nod=x; v->next=graf[y]; graf[y]=v;
    }
    while (ok==true){ford(); if (ok) update(); }
     fout<<sol;
  return(0);
}