Pagini recente » Borderou de evaluare (job #614093) | Cod sursa (job #2669301)
#include <bits/stdc++.h>
#define DIM 351
using namespace std;
ifstream fin("fmcm.in");
ofstream fout("fmcm.out");
int n,m,i,mini,nod,a,b,cap,sol,start,fina,pret;
int c[DIM][DIM], f[DIM][DIM], k[DIM][DIM];
int d[DIM], t[DIM], h[DIM];
queue<int> q;
vector<int> v[DIM];
int bellma()
{
int nod;
for(int i=1;i<=n;i++) d[i]=2000000000,h[i]=0;
d[start]=0;h[start]=1;q.push(start);
while(!q.empty())
{
nod=q.front();q.pop();h[nod]=0;
for(auto it:v[nod])
{
if(c[nod][it]>f[nod][it]&&d[it]>d[nod]+k[nod][it])
{
d[it]=d[nod]+k[nod][it],t[it]=nod;
if(!h[it]) q.push(it),h[it]=1;
}
}
}
if(d[fina]==2000000000) return 0;
else return 1;
}
int main()
{
fin>>n>>m>>start>>fina;
for(i=1;i<=m;i++)
{
fin>>a>>b>>cap>>pret;
v[a].push_back(b);v[b].push_back(a);
c[a][b]=cap;
k[a][b]=pret,k[b][a]=-pret;
}
while(bellma())
{
mini=2000000000;nod=fina;
while(t[nod])
{
mini=min(mini,c[t[nod]][nod]-f[t[nod]][nod]);
nod=t[nod];
}
nod=fina;
while(t[nod])
{
sol+=mini*k[t[nod]][nod];
f[t[nod]][nod]+=mini,f[nod][t[nod]]-=mini;
nod=t[nod];
}
}
fout<<sol;
return 0;
}