Cod sursa(job #253379)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 18:44:44
Problema Tproc Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.03 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], BUF[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);  
   
 inline 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];  
         }  
           
         if (BUF[*p][pos] == -1) {  
             complete(SAT[*p], cnt, ans, pos, *p, gr);  
             BUF[*p][pos] = ans;  
         }  
         cost += BUF[*p][pos];  
     }  
   
     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));  
     memset(BUF, 0xff, sizeof(BUF));  
     G[0].PB(1);  
     solve(0, 0, 0);  
   
     write();  
   
     return 0;  
}