Cod sursa(job #335064)

Utilizator levap1506Gutu Pavel levap1506 Data 28 iulie 2009 16:18:22
Problema Flux maxim de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.88 kb
#include <fstream>
#include <vector>
#define INF INT_MAX
#define LL long long
using namespace std;
int N,M,S,D, C[360][360], a,b,c,z,i,Heap[360],From[360],Poz[360],drum;
LL Dist[360],Sum,rez,Z[360][360],rez1;
vector<int> V[360];
vector<int>::iterator it;
void swap(int i,int j){
    int t=Heap[j];
    Heap[j]=Heap[i];
    Heap[i]=t;
    Poz[Heap[i]]=i;
    Poz[Heap[j]]=j;
}
void upheap(int i) {
    while (i/2>0&&Dist[Heap[i/2]]>Dist[Heap[i]]) {
        swap(i,i/2);
        i=i/2;
    }
}
void downheap(int i) {
    int t;
    while ((2*i<=Heap[0]&&Dist[Heap[i]]>Dist[Heap[2*i]])||(2*i+1<=Heap[0]&&Dist[Heap[i]]>Dist[Heap[2*i+1]]))
     {
        if (2*i+1<=Heap[0]) {
            if (Dist[Heap[2*i]]<Dist[Heap[2*i+1]]) t=2*i; else t=2*i+1;
        } else
        t=2*i;
        swap(i,t);
        i=t;
     }
}
void dellete(int i) {
    swap(i,Heap[0]);
    Poz[Heap[0]]=-1;
    Heap[Heap[0]--]=0;
    downheap(1);

}
int BellmanFord() {
    int i,k,unchange=0;
    for (i=1;i<=N;i++) Dist[i]=INF;
    Dist[S]=0;
    for (k=1;k<=N&&!unchange;i++) {
        unchange=1;
          for (i=1; i<=N; i++)
            for (it=V[i].begin();it!=V[i].end();it++)
              if (C[i][*it]>0&&Dist[i]+Z[i][*it]<Dist[*it])
              {
                  unchange=0;
                  Dist[*it]=Dist[i]+Z[i][*it];
              }
    }
    Sum=Dist[D];
    return 0;
}
LL Dijkstra() {
    int i;
    for (i=1;i<=N;i++)
      for (it=V[i].begin();it!=V[i].end();it++)
          if (Dist[i]!=INF && Dist[*it]!=INF) Z[i][*it]+=Dist[i]-Dist[*it];
    for (i=1;i<=N;i++){
        Dist[i]=INF;
        Heap[++Heap[0]]=i;
        Poz[i]=Heap[0];
    }
    Dist[S]=0;
    upheap(S);
    From[S]=-1;
    LL u,alt,m;
    while (Heap[0]>0) {
        u=Heap[1];
        dellete(1);
        for (it=V[u].begin();it!=V[u].end();it++) {
            alt=Dist[u]+Z[u][*it];
            if (C[u][*it]>0&&alt<Dist[*it]) {
                Dist[*it]=alt;
                upheap(Poz[*it]);
                From[*it]=u;
            }
        }
    }
    m=INT_MAX;
    u=D;
    if (Dist[D]!=INF) {
        drum=1;
        while (From[u]>0) {
            m=min(m,(long long)C[From[u]][u]);
            u=From[u];
        }
        u=D;
        while (From[u]>0)
            {
                C[From[u]][u]-=m;
                C[u][From[u]]+=m;
                u=From[u];
            }

        Sum+=Dist[D];
        return (long long)m*Sum;
    }
    return 0;
}

int main () {
    ifstream in;
    ofstream out;
    in.open("fmcm.in");
    out.open("fmcm.out");
    in >> N >> M >> S >> D;
    for (i=0;i<M;i++) {
        in >> a >> b >> c >> z;
        C[a][b]=c;
        Z[a][b]=z;
        Z[b][a]=-z;
        V[a].push_back(b);
        V[b].push_back(a);
    }



    BellmanFord();
    drum=1;
    rez=0;

    while (drum) {
        drum=0;
        rez1=Dijkstra();
        out << rez1 << " " << Sum << "\n";
        rez+=rez1;
    }
    out << rez;
    out.close();
}