Pagini recente » Cod sursa (job #976651) | Cod sursa (job #2960782) | Cod sursa (job #1434427) | Cod sursa (job #1966464) | Cod sursa (job #2048499)
#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#define file "fmcm"
#define N 355
#define oo 1e7
using namespace std;
ifstream fin(file".in");
ofstream fout(file".out");
int n,m,s,d,x,y,c,z;
int cc[N][N],zz[N][N],f[N][N];// cc - capacitate, zz - cost, f - flux
int Min = 0; //cel mai negativ cost
int ant[N],dist[N];
priority_queue<pair<int,int> > q;
vector<int> g[N]; //muchii
bitset<N> viz;
void citire()
{
fin>>n>>m>>s>>d;
while(m--)
{
fin>>x>>y>>c>>z;
g[x].push_back(y);
g[y].push_back(x);
cc[x][y] = c;
//cc[y][x] = 0
zz[x][y] = z;
zz[y][x] = -z;
Min = min(Min, min(z,-z));
}
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
zz[i][j] -= Min;
}
inline int Dijkstra()
{
viz.reset();
for(int i=1; i<=n; ++i)
dist[i] = oo;
dist[s] = 0;
q.push(make_pair(0,s));
int nod,nodurm,costurm;
while(!q.empty())
{
nod = q.top().second;
q.pop();
if(viz[nod] == 1) continue;
viz[nod] = 1;
for(int i=0; i<g[nod].size(); ++i)
{
nodurm = g[nod][i];
costurm = zz[nod][nodurm];
if(dist[nodurm] > dist[nod] + costurm && cc[nod][nodurm] - f[nod][nodurm] > 0)
{
ant[nodurm] = nod;
dist[nodurm] = dist[nod] + costurm;
q.push(make_pair(-dist[nodurm],nodurm));
}
}
}
int fluxmin = oo;
for(int nod = d; nod != s; nod = ant[nod])
fluxmin = min(fluxmin,cc[ant[nod]][nod] - f[ant[nod]][nod]);
int ctm = 0;
for(int nod = d; nod != s; nod = ant[nod],++ctm)
{
f[ant[nod]][nod] += fluxmin;
f[nod][ant[nod]] -= fluxmin;
}
return fluxmin * (dist[d]-3*Min);
}
int main()
{
citire();
int flux = 0,sol = 0;
do
{
flux += sol;
sol = Dijkstra();
}while(sol != 0);
fout<<flux<<"\n"<<Min;
return 0;
}