# Cod sursa(job #2595659)

Utilizator Data 8 aprilie 2020 10:05:18 Traseu 100 cpp-64 done Arhiva de probleme 2.5 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 60;
const int INF = 1e9;

int N, M;
vector <int> g[NMAX + 2];
int inDeg[NMAX + 2], outDeg[NMAX + 2];

int capacity[NMAX + 2][NMAX + 2], cost[NMAX + 2][NMAX + 2], flow[NMAX + 2][NMAX + 2];
int costTo[NMAX + 2], flowTo[NMAX + 2], bef[NMAX + 2];

bool Bellman()
{
for(int i = 0; i <= N + 1; i++)
costTo[i] = flowTo[i] = INF;

queue <int> Q;
Q.push(0);
costTo[0] = 0;

///HMM
long long inQ = 1 << 0;

while(!Q.empty())
{
int node = Q.front();
Q.pop();
inQ ^= (1LL << node);

for(auto it : g[node])
if(flow[node][it] < capacity[node][it])
if(costTo[it] > costTo[node] + cost[node][it])
{
costTo[it] = costTo[node] + cost[node][it];
flowTo[it] = min(flowTo[node], capacity[node][it] - flow[node][it]);

bef[it] = node;

if(inQ & (1LL << it))
continue;

Q.push(it);
inQ |= (1LL << it);
}
}

return (costTo[N + 1] != INF);
}

long long GetMinCostMaxFlow()
{
long long minCost = 0;

while(Bellman())
{
for(int node = N + 1; node != 0; node = bef[node])
{
flow[bef[node]][node] += flowTo[N + 1];
flow[node][bef[node]] -= flowTo[N + 1];
}

minCost += 1LL * flowTo[N + 1] * costTo[N + 1];
}

return minCost;
}

int main()
{
fin >> N >> M;

int totalEdgeCost = 0;
for(int i = 1; i <= M; i++)
{
int x, y, z;
fin >> x >> y >> z;

outDeg[x]++;
inDeg[y]++;

g[x].push_back(y);
g[y].push_back(x);

///HMM
cost[x][y] = z;
cost[y][x] = -z;

capacity[x][y] = INF;

totalEdgeCost += z;
}

for(int i = 1; i <= N; i++)
if(inDeg[i] > outDeg[i])
{
g[0].push_back(i);
g[i].push_back(0);

capacity[0][i] = inDeg[i] - outDeg[i];
}
else if(inDeg[i] < outDeg[i])
{
g[i].push_back(N + 1);
g[N + 1].push_back(i);

capacity[i][N + 1] = outDeg[i] - inDeg[i];
}

fout << totalEdgeCost + GetMinCostMaxFlow() << '\n';

return 0;
}