Cod sursa(job #371534)

Utilizator savimSerban Andrei Stan savim Data 5 decembrie 2009 17:56:12
Problema Cuplaj maxim de cost minim Scor Ascuns
Compilator cpp Status done
Runda Marime 2.39 kb
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

#define MAX_N 710
#define inf 2000000000
#define pb push_back

int n, m, e, dest, sol, nr, improve;
int Q[MAX_N * MAX_N], tata[MAX_N], dist[MAX_N], use[MAX_N];
int C[MAX_N][MAX_N], F[MAX_N][MAX_N], edge[MAX_N][MAX_N];

vector <int> v[MAX_N], cost[MAX_N];

void cit() {
	scanf("%d %d %d", &n, &m, &e);
	for (int i = 1; i <= e; i++) {
		int p, q, val;
    	scanf("%d %d %d", &p, &q, &val);
		p++; q += n + 1;

		v[p].pb(q); cost[p].pb(val);
		v[q].pb(p); cost[q].pb(-val);

		edge[p][q] = i;	
		C[p][q] = 1;
	}
}

void build_graph() {
	//sursa este nodul 1, destinatia n + m + 2
	dest = n + m + 2;
	for (int i = 2; i <= n + 1; i++) {
    	v[1].pb(i); cost[1].pb(0);
		v[i].pb(1); cost[i].pb(0);

		C[1][i] = 1;
	}
	for (int i = n + 2; i <= n + m + 1; i++) {
    	v[i].pb(dest); cost[i].pb(0);
		v[dest].pb(i); cost[dest].pb(0);
		
		C[i][dest] = 1;
	}
}

int bellman_ford() {
	for (int i = 1; i <= dest; i++) {
    	dist[i] = inf;
		tata[i] = -1;
		use[i] = 0;
	}
	dist[1] = 0; use[1] = 1;

	int st = 0, dr = 1; Q[1] = 1;
	while (st < dr) {
    	st++;

		int len = v[Q[st]].size();
		for (int i = 0; i < len; i++) {
			if (C[Q[st]][v[Q[st]][i]] > F[Q[st]][v[Q[st]][i]] && dist[v[Q[st]][i]] > dist[Q[st]] + cost[Q[st]][i]) {
				dist[v[Q[st]][i]] = dist[Q[st]] + cost[Q[st]][i];
				tata[v[Q[st]][i]] = Q[st];

				if (!use[v[Q[st]][i]]) {
					Q[++dr] = v[Q[st]][i];
					use[v[Q[st]][i]] = 1;
				}
			}
		}
	
		use[Q[st]] = 0;
	}

    if (dist[dest] < inf) {
		int flux = inf;
		for (int i = dest; i != 1; i = tata[i])
			flux = min(flux, C[tata[i]][i] - F[tata[i]][i]);

		for (int i = dest; i != 1; i = tata[i]) {
			F[tata[i]][i] += flux;
			F[i][tata[i]] -= flux;
		}

		return flux * dist[dest];	
	}
	return 0;
}

void solve() {
	//construiesc graful de flux
	build_graph();

	improve = 1;
	while (improve) {
    	improve = bellman_ford();
		sol += improve;
	}
}

void write() {
	for (int i = 2; i <= n + 1; i++)
		for (int j = n + 2; j < dest; j++)
			if (C[i][j] && F[i][j]) {
				nr++;
				break;
			}

	printf("%d %d\n", nr, sol);
	for (int i = 2; i <= n + 1; i++)
        for (int j = n + 2; j < dest; j++)
            if (C[i][j] && F[i][j]) {
				printf("%d ", edge[i][j]);
                break;
            }
	printf("\n");
}

int main() {
	freopen("cmcm.in", "r", stdin);
	freopen("cmcm.out", "w", stdout);

	cit();
	solve();
	write();

	return 0;
}