Cod sursa(job #961266)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 20:21:52
Problema Tproc Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.95 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; 
}