Cod sursa(job #2246712)

Utilizator Data 27 septembrie 2018 14:02:29 Flux maxim de cost minim 40 cpp done Arhiva educationala 1.74 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
#define MAX 400
#define INF 1000000000
ifstream fin("fmcm.in");
ofstream fout("fmcm.out");

typedef vector<int>::iterator iter;

int Cap[MAX][MAX], Cost[MAX][MAX], Flow[MAX][MAX];
vector<int> G[MAX];
queue<int> Q;
int dist[MAX], p[MAX];
int totalFlow = 0;
int n;
bool bfs(int s, int d){
int i;
for(i = 1 ; i <= n ; i++)
dist[i] = INF;
memset(p, 0, sizeof(p));
dist[s] = 0;
Q.push(s);

while(Q.size()) {
int node = Q.front();
Q.pop();
for(iter it = G[node].begin() ; it != G[node].end() ; it++) {
if(dist[node] + Cost[node][*it] < dist[*it] && Cap[node][*it] > Flow[node][*it]) {
dist[*it] = dist[node] + Cost[node][*it];
p[*it] = node;
if(*it == d)
break;
Q.push(*it);

}
}
}
if(dist[d] == INF)
return 0;

int flux = INF;

for(int i = d ; i != s ; i = p[i]) {
flux = min(flux, Cap[p[i]][i] - Flow[p[i]][i]);
}
for(int i = d ; i != s ; i = p[i]) {
Flow[p[i]][i] += flux;
Flow[i][p[i]] -= flux;
}
totalFlow += flux * dist[d];

return 1;
}

int main(){
int m, i, j, s, d;
fin >> n >> m >> s >> d;

while(m--){
int x, y, c, z;
fin >> x >> y >> c >> z;
G[x].push_back(y);
G[y].push_back(x);
//        cout << x << " " << y << "\n";
Cap[x][y] += c;
Cost[x][y] += z;
Cost[y][x] -= z;
Flow[x][y] = 0;
}

while(bfs(s, d)) {

}
fout << totalFlow << "\n";
}
``````