Cod sursa(job #132985)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 7 februarie 2008 01:47:53
Problema Tproc Scor Ascuns
Compilator cpp Status done
Runda Marime 1.96 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#include <vector>
using namespace std;

#define NMAX 501
#define MMAX 501
#define KMAX 10
#define MAX_PERM 10001
#define INF 666666666

vector<int> edge[MMAX];
int A[MMAX][MMAX];
int col[MMAX], mincol[MMAX], used[MMAX], p[MMAX];
int i, j, k, q, N, M, P, c, co, sco, extracost, cmin, maxcols, sum;
int sextra[MMAX][KMAX], ord[MMAX][KMAX];

void bkt(int niv)
{
	int c, c2, c3;

	if (niv > M)
	{
		cmin = sum;
		printf("cmin=%d\n", cmin);
	}
	else
	{
		// calculeaza toate sumele 'sextra'
		for (c = 1; c <= maxcols; c++)
		{
			sextra[niv][c] = 0;

			for (i = 1; i < niv; i++)
				if (col[i] == c)
					sextra[niv][c] += A[i][niv];
		}

		// ordoneaza culorile in ordine crescatoare a valorilor 'sextra'
		for (c = 1; c <= maxcols; c++)
			ord[niv][c] = c;

		for (c = 1; c < maxcols; c++)
			for (c2 = c + 1; c2 <= maxcols; c2++)
				if (sextra[niv][ord[niv][c]] > sextra[niv][ord[niv][c2]])
				{
					// swap
					c3 = ord[niv][c]; ord[niv][c] = ord[niv][c2]; ord[niv][c2] = c3;
				}

		// bkt
		for (c = 1; c <= maxcols; c++)
		{
			col[niv] = ord[niv][c];
			sum += sextra[niv][col[niv]];

			if (sum < cmin)
				bkt(niv + 1);

			sum -= sextra[niv][col[niv]];
		}
	}
}

int main()
{
	freopen("tproc.in", "r", stdin);

	scanf("%d %d %d", &N, &M, &maxcols);

	// ignora structura arborelui
	for (k = 1; k < N; k++)
		scanf("%d %d", &i, &j);

	// ignora membership information
	for (k = 1; k <= N; k++)
	{
		scanf("%d", &q);
		for (i = 1; i <= q; i++)
			scanf("%d", &j);
	}

	for (i = 1; i <= M; i++)
		edge[i].clear();

	scanf("%d", &P);

	memset(A, 0, sizeof(A));

	for (k = 1; k <= P; k++)
	{
		scanf("%d %d %d", &i, &j, &c);
		edge[i].push_back(j);
		edge[j].push_back(i);

		A[i][j] = A[j][i] = c;
	}

	cmin = INF;
	sum = 0;
	bkt(1);

	freopen("tproc.out", "w", stdout);
	printf("%d\n", cmin);

	return 0;
}