Cod sursa(job #1548107)

Utilizator kassay_akosKassay Akos kassay_akos Data 10 decembrie 2015 15:21:13
Problema Flux maxim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb

#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
const int nmax = 1003;
vector < int > v[nmax];
int cost[nmax][nmax], n, m;
int used[nmax][nmax];
int Q[nmax], father[nmax],vis[nmax];

bool BFS();

int main(){
	freopen("maxflow.in", "r", stdin);
	freopen("maxflow.out", "w", stdout);
	//memset(cost, 0, sizeof(cost));
	//memset(used, 0, sizeof(used));

	scanf("%d %d", &n, &m);
	int x, y, c;
	for (; m--;){
		scanf("%d %d %d", &x, &y, &c);
		v[x].push_back(y); v[y].push_back(x);
		cost[x][y] = c;
	}

	int maxflow = 0,fmin;
	while (BFS()){
		for (int nod : v[n]){
			int tmp = nod;
			if (cost[nod][n] - used[nod][n] == 0 || !vis[nod]) continue;			// DONT FORHET TO CHECH THE vis AS WELL
			
			fmin = cost[nod][n] - used[nod][n];
			for (; nod != 1; nod = father[nod])
				fmin = min(fmin, cost[father[nod]][nod] - used[father[nod]][nod]);
			
			nod = tmp;
			maxflow += fmin;
			used[nod][n] += fmin;
			used[n][nod] -= fmin;
			for (; nod != 1; nod = father[nod]){
				used[father[nod]][nod] += fmin;
				used[nod][father[nod]] -= fmin;						// THIS MADE ALL THE DIFFERANCE !!!!!!
			}
		}
	}

	
	printf("%d", maxflow);
	fclose(stdin);
	fclose(stdout);
	return 0;
}


bool BFS(){
	int nod;
	memset(father, 0, 4 * (n + 1));	
	memset(vis   , 0, 4 * (n + 1));
	Q[0] = 1;		// len
	Q[1] = 1;

	for (int i = 1; i <= Q[0]; i++) {
		nod = Q[i];
		if (nod == n) continue;
		for (int endP : v[nod]) {
			if (cost[nod][endP] - used[nod][endP] > 0 && !vis[endP]) {
				Q[++Q[0]] = endP;
				father[endP] = nod;
				vis[endP] = 1;
			}
		}
	}
	return vis[n];
}