fork download

copy

#include <bits/stdc++.h>
using namespace std;
int _test, TEST_FROM = INT_MIN, TEST_TO = INT_MAX;
 
const int MAX = 1010;
int color[MAX][32];
int N, K, P;
vector<int> adjw[MAX];
vector<int> tree[MAX];
 
void Dfs(int i, int par) {
  for (auto x : adjw[i])
    if (x != par) {
      tree[i].push_back(x);
      Dfs(x, i);
    }
}
void ReadInput() {
  scanf("%d %d %d", &N, &K, &P);
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < K; ++j)
      scanf("%d ", &color[i][j]);
    adjw[i].clear();
    tree[i].clear();
  }
  int a, b;
  for (int i = 1; i < N; ++i) {
    scanf("%d %d", &a, &b);
    --a, --b;
    adjw[a].push_back(b);
    adjw[b].push_back(a);
  }
  Dfs(0, -1);
}
 
long long dp[MAX][32][32];
 
#define FOR(i,n)        for(int i = 0 ; i < (n) ; i++)
#define Set(a, x)       memset( a, x, sizeof( a ) )
#define INF             987654321
#define MAX 60
set<pair<int,int> > h;
int cap[MAX][MAX],cost[MAX][MAX], fnet[MAX][MAX], adj[MAX][MAX], deg[MAX],pi[MAX] ,par[MAX],d[MAX];
 
#define Pot(u,v) (d[u] + pi[u] - pi[v])
inline void add( int v , int dis , int d_old ) {                
        pair<int,int> p(dis,v) , old( d_old , v);       h.erase(old);           h.insert( p );
}
bool dijkstra( int n, int s, int t ) {
        Set( d, 0x3F ) ;   Set( par, -1 );   h.clear();  par[s] = n ;  d[s] = 0; add( s , 0 , 0 );
 
        while( h.size() ) {
                int old, u = h.begin()->second;         h.erase(h.begin());
 
                for( int k = 0, v = adj[u][k]   ;   old = d[v] , k < deg[u]  ;  v = adj[u][++k] ){      
                        if( fnet[v][u] && d[v] > Pot(u,v) - cost[v][u] )                
                                d[v] = Pot(u,v) - cost[v][par[v] = u];
                        if( fnet[u][v] < cap[u][v] && d[v] > Pot(u,v) + cost[u][v] )    
                                d[v] = Pot(u,v) + cost[par[v] = u][v];
                        if( par[v] == u )
                                add( v , d[v], old );
                } }
        for( int i = 0; i < n; i++ )   if( pi[i] < INF )   pi[i] += d[i];
        return par[t] >= 0;
}
int mcmf( int n, int s, int t, int &fcost ) {
        Set( deg, 0 );  Set( fnet, 0 );  Set( pi, 0 );
        int i , j , bot , u , v , flow = fcost = 0;
        FOR(i,n) FOR(j,n) if( cap[i][j] || cap[j][i] ) adj[i][deg[i]++] = j;
 
        for( ; dijkstra( n, s, t ) ; flow += bot ) {
                for( bot = INF , v = t, u = par[v]; v != s; u = par[v = u] )
                        bot = min( bot , fnet[v][u] ? fnet[v][u] : ( cap[u][v] - fnet[u][v] ));
 
                for( v = t , u = par[v] ;   v != s  ;   u = par[ v = u ]  )
                        if( fnet[v][u] ) { fnet[v][u] -= bot; fcost -= bot * cost[v][u]; }
                        else             { fnet[u][v] += bot; fcost += bot * cost[u][v]; }    
        }  
        return flow;
}
 
int Match(int v, int pc, int vc) {
  int w = 0;
  map<int, int> ind;
  int n = tree[v].size();
  for (auto x : tree[v]) 
    ind[x] = ++w;
  int source = 0;
  int sink = n + K + 1;
  int ng = sink+1;
  Set(cap, 0);
  for (int i = 1; i <= n; ++i) {
    cap[source][i] = 1;
    cost[source][i] = 0;
  }
  for (int i = 1; i <= K; ++i) {
    cap[n+i][sink] = 1;
    cost[n+i][sink] = 0;
  }
  for (auto x : tree[v]) {
    for (int c = 0; c < K; ++c) {
      if (c != pc) {
        cap[ind[x]][n+c+1] = 1;
        cost[ind[x]][n+c+1] = dp[x][c][vc];
      }
    }
  }
  int fcost = 0;
  int res = mcmf(ng, source, sink, fcost);
  if (res != n)
    return 1 << 29;
  return fcost;
}
 
long long Go(int i, int c, int pc) {
  long long &ret = dp[i][c][pc];
  if (ret != -1)
    return ret;
  long long sum = color[i][c];
 
  for (auto x : tree[i]) {
    long long u = 1LL << 60;
    for (int d = 0; d < K; ++d) {
      u = min(u, Go(x, d, c));
    }
    sum += u;
  }
  sum += P;
  int am = tree[i].size() + (pc < K);
  if (am <= K) {
    sum = min(sum, (long long)color[i][c] + Match(i, pc, c));
  }
  return ret = sum;
}
void Solve() {
  memset(dp, -1, sizeof dp);
  long long ans = 1LL << 60;
  for (int c = 0; c < K; ++c)
    ans = min(ans, Go(0, c, K));
  printf("%lld\n", ans);
}
 
int main(int argc, char* argv[]) {
  if (argc == 3) {
    TEST_FROM = atoi(argv[1]), TEST_TO = atoi(argv[2]);
  }
  int ntests;
  scanf("%d", &ntests);
  for (_test = 1; _test <= ntests; ++_test) {
    ReadInput();
    if (_test >= TEST_FROM && _test <= TEST_TO) {
      printf("Case #%d: ", _test);
      Solve();
    }
  }
  return 0;
}
 

prog.cpp: In function 'void Dfs(int, int)':
prog.cpp:12:13: error: 'x' does not name a type
   for (auto x : adjw[i])
             ^
prog.cpp:17:1: error: expected ';' before '}' token
 }
 ^
prog.cpp:17:1: error: expected primary-expression before '}' token
prog.cpp:17:1: error: expected ';' before '}' token
prog.cpp:17:1: error: expected primary-expression before '}' token
prog.cpp:17:1: error: expected ')' before '}' token
prog.cpp:17:1: error: expected primary-expression before '}' token
prog.cpp: In function 'int Match(int, int, int)':
prog.cpp:86:13: error: 'x' does not name a type
   for (auto x : tree[v]) 
             ^
prog.cpp:88:3: error: expected ';' before 'int'
   int source = 0;
   ^
prog.cpp:89:3: error: expected primary-expression before 'int'
   int sink = n + K + 1;
   ^
prog.cpp:89:3: error: expected ')' before 'int'
prog.cpp:90:12: error: 'sink' was not declared in this scope
   int ng = sink+1;
            ^
prog.cpp:93:9: error: 'source' was not declared in this scope
     cap[source][i] = 1;
         ^
prog.cpp:100:13: error: 'x' does not name a type
   for (auto x : tree[v]) {
             ^
prog.cpp:108:3: error: expected ';' before 'int'
   int fcost = 0;
   ^
prog.cpp:109:3: error: expected primary-expression before 'int'
   int res = mcmf(ng, source, sink, fcost);
   ^
prog.cpp:109:3: error: expected ')' before 'int'
prog.cpp:109:22: error: 'source' was not declared in this scope
   int res = mcmf(ng, source, sink, fcost);
                      ^
prog.cpp:110:7: error: 'res' was not declared in this scope
   if (res != n)
       ^
prog.cpp:112:10: error: 'fcost' was not declared in this scope
   return fcost;
          ^
prog.cpp: In function 'long long int Go(int, int, int)':
prog.cpp:121:13: error: 'x' does not name a type
   for (auto x : tree[i]) {
             ^
prog.cpp:128:3: error: expected ';' before 'sum'
   sum += P;
   ^
prog.cpp:129:3: error: expected primary-expression before 'int'
   int am = tree[i].size() + (pc < K);
   ^
prog.cpp:129:3: error: expected ')' before 'int'
prog.cpp:130:7: error: 'am' was not declared in this scope
   if (am <= K) {
       ^

Standard output is empty