# Cod sursa(job #2632158)

Utilizator Data 2 iulie 2020 13:44:29 Traseu 100 cpp-64 done Arhiva de probleme 3.01 kb
``````#include <bits/stdc++.h>
#define DIM 210
#define INF 2000000000
using namespace std;

int capacitate[DIM][DIM],flux[DIM][DIM],cst[DIM][DIM],dist[DIM][DIM],dp[DIM];
int g_in[DIM],g_ext[DIM],viz[DIM],t[DIM],f[DIM];
vector <int> L[DIM];
deque <int> c;
int n,m,i,j,k,x,y,cost,sursa,dest;

int bellmanFord (){

for (int i=sursa;i<=dest;i++){
dp[i] = INF;
viz[i] = t[i] = 0;
}
c.clear();
c.push_back(sursa);
viz[sursa] = 1;
dp[sursa] = 0;
while (!c.empty()){
int nod = c.front();
c.pop_front();
viz[nod] = 0;
for (auto vecin : L[nod]){
if (capacitate[nod][vecin] > flux[nod][vecin] && dp[nod] + cst[nod][vecin] < dp[vecin]){
dp[vecin] = dp[nod] + cst[nod][vecin];
t[vecin] = nod;
viz[nod] = 1;
c.push_back(vecin);
}}}
return dp[dest] != INF;
}

int main (){

ifstream cin ("traseu.in");
ofstream cout ("traseu.out");

cin>>n>>m;

for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
dist[i][j] = cst[i][j] = INF;

int sol = 0;
for (i=1;i<=m;i++){
cin>>x>>y>>cost;
g_in[y]++;
g_ext[x]++;
dist[x][y] = cost;
sol += cost;
}

for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (i != j && i != k && j != k && dist[i][k] != INF && dist[k][j] != INF)
dist[i][j] = min (dist[i][j],dist[i][k] + dist[k][j]);

sursa = 0, dest = n+1;
for (i=1;i<=n;i++){
if (g_in[i] > g_ext[i]){
L[sursa].push_back(i);
L[i].push_back(sursa);
capacitate[sursa][i] = g_in[i] - g_ext[i];
f[i] = 1; /// nodul asta il leg de sursa
//cout<<sursa<<" "<<i<<" "<<capacitate[sursa][i]<<"\n";
} else {
if (g_in[i] < g_ext[i]){
L[i].push_back(dest);
L[dest].push_back(i);
capacitate[i][dest] = g_ext[i] - g_in[i];
f[i] = 2;
//cout<<i<<" "<<dest<<" "<<capacitate[i][dest]<<"\n";
}
}
}

for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
if (f[i] == 1 && f[j] == 2){
L[i].push_back(j);
L[j].push_back(i);
capacitate[i][j] = INF;
cst[i][j] = dist[i][j];
cst[j][i] = -dist[i][j];
//cout<<i<<" "<<j<<" "<<cst[i][j]<<"\n";
}
}

while (bellmanFord()){
int x = dest, dif = INF;
while (x != sursa){
dif = min (dif,capacitate[t[x]][x] - flux[t[x]][x]);
x = t[x];
}

x = dest;
while (x != sursa){

//sol += cst[t[x]][x] * dif;

flux[t[x]][x] += dif;
flux[x][t[x]] -= dif;

x = t[x];
}

sol += dif * dp[dest];
}

cout<<sol;

return 0;
}
``````