# Cod sursa(job #2710176)

Utilizator Data 22 februarie 2021 07:55:28 Traseu 100 cpp-64 done Arhiva de probleme 2.08 kb
``````#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>

using namespace std;

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

const int MAXN = 65;
const int So = 0;
const int Si = 62;
const int oo = (1<<31)-1;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

Graph G;
int N, M, Answer, Qu[MAXN][MAXN], F[MAXN][MAXN], C[MAXN][MAXN], inG[MAXN], outG[MAXN];
queue<int> Q;
bitset<MAXN>inQ;
vector<int> D(MAXN), Father(MAXN);

inline bool Bf(int Node) {
for(fill(D.begin(), D.end(), oo), inQ.reset(), Q.push(So), D[So] = 0, inQ[So] = true ; !Q.empty() ; Q.pop(), Node = Q.front() ) {
inQ[Node] = false;
for(It it = G[Node].begin(), fin = G[Node].end() ; it != fin ; ++ it)
if(F[Node][*it] < Qu[Node][*it] && D[*it] > D[Node] + C[Node][*it]) {
D[*it] = D[Node] + C[Node][*it];
Father[*it] = Node;
if(!inQ[*it]){
Q.push(*it);
inQ[*it] = true;
}
}
}
return D[Si] != oo;
}
int main() {
cin >> N >> M;
for(int i = 1 ; i <= M ; ++ i) {
int x, y, z;
cin >> x >> y >> z;
++outG[x];
++inG[y];
G[x].push_back(y);
G[y].push_back(x);
Qu[x][y] = oo;
C[x][y] = z;
C[y][x] = -z;
}
for(int i = 1 ; i <= N ; ++ i)
if(inG[i] > outG[i])
G[So].push_back(i), Qu[So][i] = inG[i] - outG[i];
else if(inG[i] < outG[i]) G[i].push_back(Si), Qu[i][Si] = outG[i] - inG[i];
while(Bf(So)) {
int MinFlow = oo;
for(int i = Si ; i != So ; i = Father[i])
MinFlow = min(MinFlow, Qu[Father[i]][i] - F[Father[i]][i]);
for(int i = Si ; i != So ; i = Father[i])
F[i][Father[i]] -= MinFlow,
F[Father[i]][i] += MinFlow;