Pagini recente » Cod sursa (job #160736) | Cod sursa (job #2469834)
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <deque>
#include <climits>
#define DIM 400
using namespace std;
ifstream fin("fmcm.in");
ofstream fout("fmcm.out");
deque<int> q;
int i,n,m,z,c,x,y,flux[DIM][DIM],Z[DIM][DIM],r[DIM][DIM],s,d,rasp,D[DIM],T[DIM],minim,ok,nod,f[DIM];
vector<int> L[DIM];
int ford(){
for(int i=1;i<=n;i++){
D[i]=INT_MAX;
f[i]=0;
}
q.push_back(s);
D[s]=ok=0;
f[s]=1;
while(!q.empty()){
nod=q.front();
q.pop_front();
f[nod]=0;
for(int i=0;i<L[nod].size();i++){
int vec=L[nod][i];
if((D[vec]>D[nod]+Z[nod][vec])&&(r[nod][vec]>flux[nod][vec])){
D[vec]=D[nod]+Z[nod][vec];
T[vec]=nod;
if(f[vec]==0){
q.push_back(vec);
f[vec]=1;
if(vec==d)
ok=1;
}
}
}
}
return ok;
}
int main(){
fin>>n>>m>>s>>d;
for(i=1;i<=m;i++){
fin>>x>>y>>c>>z;
L[x].push_back(y);
L[y].push_back(x);
r[x][y]=c;
Z[x][y]=z;
Z[y][x]=-z;
}
while(ford()){
nod=d;
minim=INT_MAX;
while(nod!=s){
minim=min(minim,r[T[nod]][nod]-flux[T[nod]][nod]);
nod=T[nod];
}
nod=d;
while(nod!=s){
flux[T[nod]][nod]+=minim;
flux[nod][T[nod]]-=minim;
nod=T[nod];
}
rasp+=minim*D[d];
}
fout<<rasp;
return 0;
}