# Cod sursa(job #24995)

Utilizator Data 4 martie 2007 08:47:13 Traseu 100 cpp done Arhiva de probleme 3.02 kb
``````#include <cstdio>
#include <vector>

using namespace std;

#define Nmax 64
#define INF 0x3f3f3f3f
#define pb push_back
#define sz size()

int n, m, s, d, best;
int cost[Nmax][Nmax], gri[Nmax], gro[Nmax], v[Nmax], dist[Nmax], c[Nmax][Nmax], cd[Nmax * Nmax], t[Nmax];
vector<int> lv[Nmax];

void citire()
{
int i, a, b, c;
scanf("%d %d\n", &n, &m);

memset(cost, 0x3f, sizeof(cost));
for (i = 1; i <= n; ++i)
cost[i][i] = 0;

for (i = 1; i <= m; ++i)
{
scanf("%d %d %d\n", &a, &b, &c);
cost[a][b] = c;
++gro[a]; ++gri[b];
best += c;
}
}

int bellman_ford()
{
int st, dr, i, lim, nod;

memset(v, 0, sizeof(v));
memset(dist, 0x3f, sizeof(dist));

cd[dr = 1] = s;
st = 0;
dist[s] = 0;
v[s] = 1;

while (st < dr)
{
nod = cd[++st];
lim = lv[nod].sz;
v[nod] = 0;

for (i = 0; i < lim; ++i)
if (c[nod][lv[nod][i]] > 0 && dist[nod] + cost[nod][lv[nod][i]] < dist[lv[nod][i]])
{
dist[lv[nod][i]] = dist[nod] + cost[nod][lv[nod][i]];
t[lv[nod][i]] = nod;
if (!v[lv[nod][i]])
{
v[lv[nod][i]] = 1;
cd[++dr] = lv[nod][i];
}
}
}

if (dist[d] < INF / 2)
return 1;
else
return 0;
}

void flux()
{
int nod, val;

while (bellman_ford())
{
val = INF;
for (nod = d; nod != s; nod = t[nod])
val = min(val, c[t[nod]][nod]);

best += dist[d] * val;

for (nod = d; nod != s; nod = t[nod])
{
c[t[nod]][nod] -= val;
c[nod][t[nod]] += val;
}
}
}

void solve()
{
int i, j, k;
for (k = 1; k <= n; ++k)
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
if (cost[i][k] + cost[k][j] < cost[i][j])
cost[i][j] = cost[i][k] + cost[k][j];

s = 0;
d = n + 1;

for (i = 1; i <= n; ++i)
if (gri[i] > gro[i])
{
lv[s].pb(i);
lv[i].pb(s);
c[s][i] = gri[i] - gro[i];
}
else if (gri[i] < gro[i])
{
lv[i].pb(d);
lv[d].pb(i);
c[i][d] = gro[i] - gri[i];
}

for (i = 1; i <= n; ++i)
if (gri[i] > gro[i])
for (j = 1; j <= n; ++j)
if (gri[j] < gro[j])
{
lv[i].pb(j);
lv[j].pb(i);
c[i][j] = INF;
cost[j][i] = - cost[i][j];
}

for (i = 0; i <= d; ++i)
{
cost[s][i] = cost[i][s] = 0;
cost[i][d] = cost[d][i] = 0;
}

flux();

printf("%d\n", best);
}

int main()
{
freopen("traseu.in", "r", stdin);
freopen("traseu.out", "w", stdout);
citire();
solve();
return 0;
}
``````