# Cod sursa(job #116)

Utilizator Data 5 decembrie 2006 13:41:53 Traseu 0 cpp done Arhiva de probleme 2.23 kb
``````#include <cstdio>
#include <memory>
using namespace std;

const char iname[] = "traseu.in";
const char oname[] = "traseu.out";

#define MAX_N 61

int N;

int D[MAX_N][MAX_N];

int in_deg[MAX_N], out_deg[MAX_N];

int R;

int C[MAX_N][MAX_N], F[MAX_N][MAX_N], A[MAX_N][MAX_N], X[MAX_N];

int Q[MAX_N * MAX_N], P[MAX_N], V[MAX_N];

inline void add(const int x, const int y) {
A[x][++A[x][0]] = y;
}

int bellman_ford(const int srs, const int dst)
{
int x, y;
int i;

memset(X, 0, sizeof(X));
memset(V, 1, sizeof(V));
P[dst] = 0;
V[srs] = 0;
X[srs] = MAX_N;
for (i = A[x][0]; i > 0; --i) {
y = A[x][i];
if (C[x][y] - F[x][y] > 0)
if (V[y] > V[x] + D[x][y]) {
V[y] = V[x] + D[x][y];
X[ Q[++tail] = y ] = min(X[x], C[x][y] - F[x][y]);
P[y] = x;
}
}
}
if (X[dst] == 0)
return 0;
for (x = dst; x != srs; x = P[x])
F[P[x]][x] += X[dst],
F[x][P[x]] -= X[dst];

return 1;
}

int main(void)
{
freopen(iname, "r", stdin);
int M;
int i, j, k;
int x, y;

scanf("%d", & N);
for (i = 1; i <= N; ++i)
for (j = 1; j <= N; ++j)
if (i != j)  D[i][j] = int(1e9);
for (scanf("%d", & M), i = 0; i < M; ++i) {
scanf("%d %d", & x, & y);
scanf("%d", D[x] + y);
R += D[x][y];
in_deg[y]  += 1;
out_deg[x] += 1;
}
for (k = 1; k <= N; ++k)
for (i = 1; i <= N; ++i)
for (j = 1; j <= N; ++j)
if (D[i][j] > D[i][k] + D[k][j])  D[i][j] = D[i][k] + D[k][j];

for (i = 1; i <= N; ++i)
if (in_deg[i] - out_deg[i] > 0)
X[i] = -1;
else if (out_deg[i] - in_deg[i] > 0)
X[i] = +1;

for (i = 1; i <= N; ++i)
if (X[i] == -1)
else if (X[i] == +1)
add(i, N + 1), add(N + 1, i), C[i][N + 1] = out_deg[i] - in_deg[i];

for (i = 1; i <= N; ++i)
if (X[i] == -1)
for (j = 1; j <= N; ++j)
if (X[j] == +1) {
D[j][i] = - D[i][j];