Cod sursa(job #816037)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 17 noiembrie 2012 12:07:16
Problema Cuplaj maxim de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <vector>

using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}

const int INF = 1e9;

int V;
int min_cost, max_flow;
int capacity[602][602], cost[602][602], dist[602], prev[602];
bool seen[602];
int Q[602 * 602];
vector<int> G[602];
int edge[602][602];

inline void add_edge(int a, int b, int c, int d, int i) {
	capacity[a][b] = c, cost[a][b] = +d, G[a].push_back(b);
	capacity[b][a] = 0, cost[b][a] = -d, G[b].push_back(a);
	edge[a][b] = i;
}

inline void run(const int source, const int sink) {
	while (true) {
		for (int v = 0; v < V; v++) {
			prev[v] = -1;
			seen[v] = false;
			dist[v] = INF;
		}
		int front = 0, back = 0;
		Q[back++] = source;
		dist[source] = 0;
		seen[source] = true;
		while (back - front > 0) {
			int u = Q[front++];
			for (size_t i = 0; i < G[u].size(); i++) {
				int v = G[u][i];
				if (dist[u] < INF && capacity[u][v] && dist[u] + cost[u][v] < dist[v]) {
					dist[v] = dist[u] + cost[u][v];
					prev[v] = u;
					if (!seen[v]) {
						Q[back++] = v;
						seen[v] = true;
					}
				}
			}
			seen[u] = false;
		}
		if (dist[sink] == INF) {
			break;
		}
		for (int where = sink; where != source; where = prev[where]) {
			capacity[prev[where]][where]--;
			capacity[where][prev[where]]++;
		}
		min_cost += dist[sink];
		max_flow++;
	}
}

int main() {
	freopen("cmcm.in", "r", stdin);
	freopen("cmcm.out", "w", stdout);
	int c1 = next_int();
	int c2 = next_int();
	V = c1 + c2 + 2;
	int source = c1 + c2;
	int sink = c1 + c2 + 1;
	for (int i = 0; i < c1; i++) {
		add_edge(source, i, 1, 0, 0);
	}
	for (int i = 0; i < c2; i++) {
		add_edge(c1 + i, sink, 1, 0, 0);
	}
	int m = next_int();
	for (int i = 0; i < m; i++) {
		int x = next_int();
		int y = next_int();
		int z = next_int();
		add_edge(x - 1, c1 + y - 1, 1, z, i + 1);
	}
	run(source, sink);
	printf("%d\n", max_flow);
	printf("%d\n", min_cost);
	for (int i = 0; i < 602; i++) {
		for (int j = 0; j < 602; j++) {
			if (edge[i][j] && !capacity[i][j]) {
				printf("%d ", edge[i][j]);
			}
		}
	}
	return 0;
}