Pagini recente » Cod sursa (job #2092442) | Cod sursa (job #2358131) | Cod sursa (job #1385194) | Cod sursa (job #810024) | Cod sursa (job #132985)
Cod sursa(job #132985)
#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;
}