TopCoder SRM619 DIV1 MEDIUM - GoodCompanyDivOne

Source

TopCoder SRM619 DIV1 MEDIUM (600pt)
Problem Statement

問題概要

$N$ 人の社員がいて,入社したのが古い順に $0,1,2,\ldots,N-1$ と番号が付けられている.
$0$ 番以外の各社員は直属の上司が $1$ 人だけいて,社員 $k$ の上司の番号 $U_k,\;\; U_k < k$ が与えられる.
また,仕事が $M$ 種類あり,それぞれの仕事 $k$ を学ぶためのセミナーに参加するのに必要なコスト($1$人あたりのコスト) $C_k$ が与えられる.
各社員は,ちょうど $2$ つのセミナーに参加し,仕事を $2$ 種類できるようにならなければいけない.
グループが $N$ 個あって,グループ $k$ は,社員 $k$ と社員 $k$ を直属の上司とするもののみからなる.
各グループで働くときには,そのグループ内の社員が全員違う仕事を行えるようになっておかなくてはいけない.
このような条件を満たすためのセミナーの参加費用の和の最小値を求める問題.
条件をみたすことができないならそれを指摘する.

解法

$0$ をルートだと思った根付き木を考えて,DPをする.
状態を(社員の番号,その社員が絶対に学ばないといけないとした仕事の番号)とし,その社員以下のツリー(その社員の部下,部下の部下,部下の部下の部下,…)が仕事を $2$ つずつ条件をみたすように学ぶための最小コストを計算する.
DPの計算は下(下っ端の部下)から行っていく.
各DPの計算は,そのDPの状態の $1$ つ目の社員と,その直属の部下からなるグループについて考える.
誰にどの仕事を割り振るかというので,割当問題をハンガリアン法,または,最小費用流で解く.
部下たちに各仕事を割りてた場合は,DPテーブルから最小コストを拾ってきて,上司はある仕事を絶対学ぶという条件を満たすように,その仕事と,このグループでの役割の仕事を学ぶためのコストを使う.
このグループの役割として,上司に絶対学ばなくてはいけないものを割り当てる場合は,もう $1$ つの仕事はなんでも良いので,一番安いのにする.

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000

/* n <= m */
int intMinCostMatch(int **mat, int n, int m, void *workMemory){
  int i, a, b, c, r, z;
  int *toright;
  int *toleft;
  int *ofsleft;
  int *ofsright;
  int *left, *right;
  int *trace, *ptr;
  int d, t, res = 0;

  toright = (int*)workMemory; workMemory = (void*)(toright + n);
  toleft  = (int*)workMemory; workMemory = (void*)(toleft  + m);
  ofsleft  = (int*)workMemory; workMemory = (void*)(ofsleft  + n);
  ofsright = (int*)workMemory; workMemory = (void*)(ofsright + m);

  left  = (int*)workMemory; workMemory = (void*)(left  + n);
  right = (int*)workMemory; workMemory = (void*)(right + m);
  trace = (int*)workMemory; workMemory = (void*)(trace + m);
  ptr   = (int*)workMemory; workMemory = (void*)(ptr   + m);

  rep(i,n) toright[i] = -1, ofsleft[i] = 0;
  rep(i,m) toleft[i] = -1, ofsright[i] = 0;

  rep(r,n){
    rep(i,n) left[i] = 0;
    rep(i,m) right[i] = 0;
    rep(i,m) trace[i] = -1, ptr[i] = r;
    left[r] = 1;

    for(;;){
      d = INF;
      rep(i,m) if(!right[i]){
        t = mat[ptr[i]][i] + ofsleft[ptr[i]] + ofsright[i];
        if(d > t) d = t, b = i;
      }

      res += d;
      rep(i,n) if(left[i]) ofsleft[i] -= d;
      rep(i,m) if(right[i]) ofsright[i] += d;

      trace[b] = ptr[b];
      c = toleft[b];
      if(c < 0){
        while(b>=0){
          a = trace[b];
          z = toright[a];
          toleft[b] = a;
          toright[a] = b;
          b = z;
        }
        break;
      }
      right[b] = left[c] = 1;
      rep(i,m) if(mat[c][i] + ofsleft[c] + ofsright[i] < mat[ptr[i]][i] + ofsleft[ptr[i]] + ofsright[i]) ptr[i] = c;
    }
  }

/*  rep(i,n) match[i] = toright[i];*/
  return res;
}


int N, M;
vector<int> up, cost, edge[100];
int dp[100][100];
int *mat[100];
void *mem;

int solve(int node, int val){
  int i, j, k, res = INF, tmp;
  int n = edge[node].size();

  if(dp[node][val] >= 0) return dp[node][val];

  rep(k,n) {
    i = edge[node][k];
    rep(j,M) solve(i,j);
  }

  rep(k,n) {
    i = edge[node][k];
    rep(j,M) mat[k][j] = solve(i,j);
  }

  rep(j,M){
    mat[n][j] = cost[val] + cost[j];
    if(j==val){
      if(val==0) mat[n][j] = cost[0] + cost[1];
      else       mat[n][j] = cost[0] + cost[val];
    }
  }

  res = intMinCostMatch(mat, n+1, M, mem);

  return dp[node][val] = res;
}

class GoodCompanyDivOne {
public:
int minimumCost(vector <int> up_, vector <int> cost_) {
  int i, j, k;
  int res = INF, tmp;

  rep(i,100) mat[i] = (int*)malloc(100*sizeof(int));
  mem = malloc(10000000);

  up = up_;
  cost = cost_;
  N = up.size();
  M = cost.size();
  sort(cost.begin(), cost.end());

  rep(i,N) edge[i].clear();
  REP(i,1,N) edge[up[i]].push_back(i);

  rep(i,N) if(edge[i].size() + 1 > M) return -1;

  rep(i,100) rep(j,100) dp[i][j] = -1;
  rep(i,M){
    tmp = solve(0, i);
    res = min(res, tmp);
  }

  return res;
}

}

Current time: 2017年11月18日04時23分27秒
Last modified: 2014年05月10日03時27分55秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM619 SRM_Div1_Medium
トップページに戻る

Logged in as: unknown user (not login)

ログイン: