Pagini recente » Cod sursa (job #528824) | Cod sursa (job #486547) | Cod sursa (job #125812) | Cod sursa (job #248766) | Cod sursa (job #335064)
Cod sursa(job #335064)
#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();
}