Cod sursa(job #554579)

Utilizator feelshiftFeelshift feelshift Data 14 martie 2011 22:53:03
Problema Cuplaj maxim de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
// http://infoarena.ro/problema/cmcm
#include <fstream>
#include <bitset>
#include <vector>
#include <queue>
using namespace std;

#define to first
#define cost second

const int maxSize = 611;
const int oo = 0x3f3f3f3f;
const int source = 0;
const int sink = 610;

ifstream in("cmcm.in");
ofstream out("cmcm.out");

int dist[maxSize];
int father[maxSize];
int currentFlow[maxSize][maxSize];
bitset<maxSize> visit;
vector< pair<int,int> > edge;
vector< pair<int,int> > graph[maxSize];

bool bellmanFord();

int main() {
	int firstSize,secondSize,edges;

	in >> firstSize >> secondSize >> edges;
	edge.reserve(edges);

	int from,to,edgeCost;
	for(int i=1;i<=edges;i++) {
		in >> from >> to >> edgeCost;
		to += firstSize;

		graph[from].push_back(make_pair(to,edgeCost));
		graph[to].push_back(make_pair(from,-edgeCost));
		edge.push_back(make_pair(from,to));
	}

	for(int i=1;i<=firstSize;i++) {
		graph[source].push_back(make_pair(i,0));
		graph[i].push_back(make_pair(source,0));
	}

	for(int i=firstSize+1;i<=firstSize+secondSize;i++) {
		graph[i].push_back(make_pair(sink,0));
		graph[sink].push_back(make_pair(i,0));
	}

	int maxFlow = 0;
	while(bellmanFord()) {
		for(int node=sink;node!=source;node=father[node])
			if(currentFlow[father[node]][node])
				continue;

		for(int node=sink;node!=source;node=father[node]) {
			currentFlow[father[node]][node]++;
			currentFlow[node][father[node]]--;
		}

		maxFlow += dist[sink];
	}

	out << maxFlow << "\n";

	in.close();
	out.close();

	return (0);
}

bool bellmanFord() {
	visit.reset();
	visit[source] = true;

	memset(dist,oo,sizeof(dist));
	dist[source] = 0;

	int node;
	vector< pair<int,int> >::iterator it,end;

	queue<int> myQueue;
	myQueue.push(source);

	while(!myQueue.empty()) {
		node = myQueue.front();
		myQueue.pop();

		end = graph[node].end();
		for(it=graph[node].begin();it!=end;++it)
			if(!currentFlow[node][it->to] && dist[it->to] > dist[node] + it->cost) {
				dist[it->to] = dist[node] + it->cost;

				if(!visit[it->to]) {
					visit[it->to] = true;
					myQueue.push(it->to);
				}
			}

		visit[node] = false;
	}

	return (dist[sink] != oo);
}