Mai intai trebuie sa te autentifici.
Cod sursa(job #3297364)
| Utilizator | Data | 22 mai 2025 15:23:06 | |
|---|---|---|---|
| Problema | Flux maxim | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.79 kb |
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1000;
const int INF = 1e9;
int flux[NMAX + 1][NMAX + 1];
vector <int> edges[NMAX + 1];
int viz[NMAX + 1];
int minDist[NMAX + 1];
int firstGood[NMAX + 1];
int s, d;
bool bfs() {
for ( int i = s; i <= d; i ++ ) minDist[i] = INF;
minDist[s] = 0;
queue <int> q;
q.push( s );
while ( !q.empty() ) {
int node = q.front();
q.pop();
for ( auto vec : edges[node] ) {
if ( flux[node][vec] > 0 && minDist[node] + 1 < minDist[vec] ) {
minDist[vec] = minDist[node] + 1;
q.push( vec );
}
}
}
return minDist[d] != INF;
}
int pushFlow( int node, int f ) {
if ( f == 0 || node == d ) return f;
for ( int& i = firstGood[node]; i < (int)edges[node].size(); i ++ ) {
int vec = edges[node][i];
if ( minDist[vec] == minDist[node] + 1 ) {
int aux = pushFlow( vec, min( f, flux[node][vec] ) );
if ( aux > 0 ) {
flux[node][vec] -= aux;
flux[vec][node] += aux;
return aux;
}
}
}
return 0;
}
int main() {
ifstream fin( "maxflow.in" );
ofstream fout( "maxflow.out" );
int n, m;
fin >> n >> m;
for ( int i = 1, a, b, c; i <= m; i ++ ) {
fin >> a >> b >> c;
edges[a].push_back( b );
edges[b].push_back( a );
flux[a][b] = c;
}
s = 1;
d = n;
int maxFlow = 0;
while( bfs() ) {
for ( int i = 1; i <= n; i ++ ) {
firstGood[i] = viz[i] = 0;
}
int f;
while ( (f = pushFlow( s, INF )) ) {
maxFlow += f;
}
}
fout << maxFlow;
return 0;
}