# Cod sursa(job #2611755)

Utilizator Data 7 mai 2020 16:06:47 Traseu 30 cpp-64 done Arhiva de probleme 2.49 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 410;

ifstream fin("traseu.in");
ofstream fout("traseu.out");

int n, m;
int gin[N], gout[N];

//original graph
namespace og{
int dist[N][N];

void nuke(){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(i != j){
dist[i][j] = INF;
}
}
}
}

void royfloy(){
for(int a = 1; a <= n; ++a){
for(int b = 1; b <= n; ++b){
for(int i = 1; i <= n; ++i){
dist[a][b] = min(dist[a][b], dist[a][i]+dist[i][b]);
}
}
}
}
}

int s, d;
void setup(){
s = 0;
d = n+1;
og::nuke();
}

int ans = 0;
fin >> n >> m;
setup();
for(int i = 0; i < m; ++i){
int a, b, v;
fin >> a >> b >> v;
og::dist[a][b] = v;
ans += og::dist[a][b];
gout[a]++;gin[b]++;
}
}

//bipartite graph
namespace bp{
int cap[N][N], flo[N][N];
int cst[N][N];
vector<int> gra[N];

void biparthick(){
for(int a = 1; a <= n; ++a){
int da = gin[a]-gout[a];
if(da > 0){
cap[s][a] = da;
gra[s].push_back(a);
}else if(da < 0){
cap[a][d] = -da;
gra[a].push_back(d);
}

for(int b = 1; b <= n; ++b){
int db = gin[b]-gout[b];
if(da > 0 && db < 0){
cst[a][b] = og::dist[a][b];
cst[b][a] = -cst[a][b];

gra[a].push_back(b);
gra[b].push_back(a);

cap[a][b] = INF;
}
}
}
}

queue<int> q;
bool inq[N];
void bellnuke(){
for(int a = s; a <= d; ++a){
dist[a] = INF;
}
}

bool bellman(){
bellnuke();
q.push(s);
dist[s] = 0;
while(!q.empty()){
int a = q.front();q.pop();
inq[a] = false;
for(auto b : gra[a]){
int v = dist[a]+cst[a][b];
if(v < dist[b] && flo[a][b] < cap[a][b]){
dist[b] = v;
if(!inq[b]){
q.push(b);
inq[b] = true;
}
}
}
}
return dist[d] != INF;
}

void maxflow(){
int fmin = INF;
for(int x = d; x != s; x = dad[x]){
}
for(int x = d; x != s; x = dad[x]){
}
ans += dist[d]*fmin;
}

void flowerize(){
while(bellman()){
maxflow();
}
}
}

void solve(){
og::royfloy();
bp::biparthick();
bp::flowerize();
}

int main(){
// ios_base::sync_with_stdio(false);