Cod sursa(job #194568)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 11 iunie 2008 23:54:01
Problema Tproc Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int VMAX = 4200;
const int NMAX = 512;
const int KMAX = 8;
const int INF = 0x3f3f3f3f;

#define FORI(p, X) for (typeof((X).begin()) p = (X).begin(); p != (X).end(); ++p)
#define PB push_back

int N, M, K, P, NP;
int INC[NMAX][NMAX], SAT[NMAX];
vector <int> G[NMAX], T[NMAX], PERM[VMAX];
int used[KMAX], D[NMAX][VMAX];
int jump[KMAX][KMAX][VMAX];

void read(void) {
	ifstream fin("tproc.in");
	int i, j, u, v, c, cnt;

	fin >> M >> N >> K;

	for (i = 1; i < M; ++i) {
		fin >> u >> v;
		G[u].PB(v); G[v].PB(u);
	}

	for (i = 1; i <= M; ++i) {
		fin >> cnt;
		T[i].resize(cnt);
		for (j = 0; j < cnt; ++j)
			fin >> T[i][j];
	}

	fin >> P;

	for (i = 0; i < P; ++i) {
		fin >> u >> v >> c;
		INC[u][v] = INC[v][u] = c;
	}

	fin.close();
}

void DFS(int k, int t) {	
	FORI(p, G[k])
		if (*p != t)
			DFS(*p, k);
	
	if (t) {
		int d = 0;
		FORI(p, T[k]) {
			FORI(q, T[t])
				if (*p == *q) {
					swap(*p, T[k][d++]);
					break;
				}
		}
		SAT[k] = d;
	}
}

void back(vector <int> V, int k) {
	if ((int) V.size() == KMAX) {
		PERM[NP++] = V;
	} else {
		int i;

		V.PB(0);
		for (i = 0; i <= k && i < K; ++i)
			*V.rbegin() = i,
			back(V, max(k, i+1));
	}
}

int solve(int, int, int);

void complete(int k, int v, int &ans, int pos, int call, int tata) {
	int i;

	if (k == (int) T[call].size()) {
		ans = min(ans, solve(call, pos, tata));
	} else {
		for (i = 0; i <= v && i < K; ++i)
			complete(k+1, max(v, i+1), ans, jump[k][i][pos], call, tata);
	}
}

int solve(int gr, int op, int tata) {
	if (D[gr][op] != -1)
		return D[gr][op];

	int i, j, u, cost = 0;
/*
	for (i = 0; i < (int) T[gr].size(); ++i)
		for (j = max(i+1, SAT[gr]); j < (int) T[gr].size(); ++j)
			if (PERM[op][i] == PERM[op][j])
				cost += INC[ T[gr][i] ][ T[gr][j] ];
*/
	FORI(p, G[gr]) {
		if (*p == tata) continue;
			
		memset(used, 0xff, sizeof(used));
		int cnt = 0, ans = INF, pos = 0, v;

		for (i = 0; i < SAT[*p]; ++i) {
			for (j = 0; T[gr][j] != T[*p][i]; ++j);
			u = PERM[op][j];
			v = ( (used[u] == -1 ? (used[u] = cnt++) : used[u]) );
			pos = jump[i][v][pos];
		}

		complete(SAT[*p], cnt, ans, pos, *p, gr);
		cost += ans;
	}

	return D[gr][op] = cost;
}

void write(void) {
	ofstream fout("tproc.out");

	fout << D[0][0] << '\n';

	fout.close();
}

void prep(vector <int> V, int p, int k) {
	if ((int) V.size() == KMAX) return;
	int i, q;

	V.PB(0);
	for (i = 0; i <= k && i < K; ++i) {
		*V.rbegin() = i;
	
		q = lower_bound(PERM + p, PERM + NP, V) - PERM;

		jump[V.size() - 1][i][p] = q;
		
		prep(V, q, max(k, i+1));
	}

}

int main(void) {

	read();

	DFS(1, 0);

	back(vector <int> (), 0);

	prep(vector <int> (), 0, 0);

	memset(D, 0xff, sizeof(D));
	G[0].PB(1);
	solve(0, 0, 0);

	write();

	return 0;
}