WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM619 Div1 Medium "GoodCompanyDivOne"

問題

TopCoder Statistics - Problem Statement

シャイニーは会社を経営していた。そこにはN人の社員がいる。社員は入社した順に0~N-1と番号が付けられている。

社員0は上司を持たないただ1人の社員である。他の社員は直属の上司を1人持っている。あなたはN個の要素を持つint superiorが与えられる。0番目の要素は-1であり、これは0番目の社員が上司を持たないことを表している。iが1~N-1でのsuperior[i]は、i番目の社員の上司の番号を表している。

上司はその部下よりも入社が早いため、superior[i] < iとなっている。

現在、社員達はこれといって仕事ができない。シャイニーはこの状況を変えたいと思っている。彼女は社員達に仕事を行うためのトレーニング受けてもらい、かかった費用を支払うことに決めた。具体的には、それぞれの社員には、2種類のトレーニングを受けてもらうことにした。

K種類の仕事があり、それを行えるようになるためのトレーニングもK種類ある。あなたはK個の要素を持つint training が与えられる。training[i]はi番目のトレーニング受けるときにかかる費用を表している。もし複数の社員が同じトレーニングを受けた場合、それぞれの社員に費用を支払わなければならない。

それぞれの社員は部署に所属している。社員xの部署は社員xとその直属の部下によって構成される。正確には、xでない任意の社員をyとしたときに、superior[y] = xとなるようなyがxの部署に所属している。もしsuperior[z] = yかつsuperior[y] = xとなっていても、zはxの部署に所属しないことに注意して欲しい。

シャイニーはオールラウンダーな部署が好きである。オールラウンダーな部署とは

・部署内の社員は何か仕事を行っており、かつ
・同じ仕事をしている社員がいないことである。

シャイニーはそれぞれの部署をチェックするため、部署にいる社員達は部署がオールラウンドであるように、仕事を選ぶ。もし、それが出来たならば、シャイニーはこの部署はgoodと評価する。

シャイニーはN個の部署全てがgoodであれば、会社もgoodであると評価する。(全ての部署が、同じタイミングでgoodである必要はないことに注意して欲しい。各部署は、あるタイミングでオールラウンドにすることができるのであれば、会社としてgoodとなる)

シャイニーはそれぞれの社員に、どのトレーニングを受けてもらうかを決めなくてはならない。彼女は会社をgoodとしたかったが、それによる費用は最小限に抑えたかった。

もし、シャイニーの会社をgoodとすることができるのであれば、それにかかる必要最小限の費用を返せ。そうでなければ-1を返せ。

制約

1 <= superior.size <= 30
2 <= training.size <= 30
1 <= training[i] <= 100


Petrさんのソースコードを見て

まず、自分は貪欲でいけると勘違いしました。
とりあえずtrainingを昇順でソートしておく。あとは同じタイミングで全部署をオールラウンダーにしなくていいんだから、例えば5人いる部署にはボスから順番にtrainingの0, 1, 2, 3, 4を振ってけばいいんじゃないの~と考えたけど、落とし穴がある。
具体的には、下記のような上下関係があったときに、こんな感じでトレーニングさせればいいかなと思ってたけど・・・
f:id:Ekaing:20140506184226j:plain

下段右の社員は2をやらせなくてもよい。なぜならその上司は既に2の仕事を覚えているから
f:id:Ekaing:20140506184234j:plain


というわけで、貪欲はちょっと厳しいので、DPをする。

dp[i][j] := i番目の社員をルートとしたサブツリーで、i番目の社員にj番目のトレーニングを習わせて仕事もさせたときの最小費用

社員それぞれに2つトレーニングさせて、シャイニーがチェックしに来たときにどちらか仕事を選ばせることができるが、実は仕事を1つに固定しちゃっていいような気がする・・・。ここらへんがあいまいだけど、(0, 3)の仕事が出来る社員に、1回3の仕事をやらせましたって時に、次回0の仕事をやらせる意味はない気がする。

更新の仕方が問題で、愚直にやると(部下の数!)の計算量になってしまうため、下記の様に最小費用流でもとめる。
BOSSのやりたい仕事はBOSSだけに任せ、残りの仕事を部下にどう割り振ればよいか決めさせれば良い。
f:id:Ekaing:20140506184244j:plain


ソースコード

class MinCostFlow {
public:
    MinCostFlow(int vertexNumber);
    ~MinCostFlow();
    void addEdge(int v, int u, int cap, int cost);
    int flow(int s, int t, int f);
    static const int INF;
private:    
    int m_vNum;
    struct E { int to, cap, cost, rev; };
    vector<E> *G;
    int *dist, *prevv, *preve;
};

const int INF = MinCostFlow::INF;
const int MAX_N = 35;
vector<int> S, T;
int SN, TN;
int dp[MAX_N][MAX_N];
vector<int> G[MAX_N];

class GoodCompanyDivOne {
public:

    void dfs(int cur) {
        // まず部下のdpを完成させる
        for (int i = 0; i < G[cur].size(); i++) {
            dfs(G[cur][i]);
        }

        int dn = G[cur].size(); // 部下の人数

        // 自分が受け持つ仕事がiだったら・・・
        for (int i = 0; i < TN; i++) {
            int vn = dn + TN + 3;
            MinCostFlow mcf(vn);
            int s = vn - 2;
            int t = vn - 1;
            // s->training
            for (int j = 0; j < TN; j++) {
                mcf.addEdge(s, j, 1, 0);
            }

            // training->superior
            for (int j = 0; j < TN; j++) {
                if (i == j) {
                    // 上司のみ
                    int cost = T[j] + (j == 0 ? T[1] : T[0]);
                    mcf.addEdge(j, TN + dn, 1, cost);
                }
                else{
                    // 部下全員分
                    for (int k = 0; k < dn; k++) {
                        if (dp[G[cur][k]][j] == INF) continue;
                        mcf.addEdge(j, TN + k, 1, dp[G[cur][k]][j]);
                    }
                }                
            }

            // superior->t
            for (int j = 0; j <= dn; j++) {
                mcf.addEdge(TN + j, t, 1, 0);
            }

            // 最小費用流
            dp[cur][i] = mcf.flow(s, t, dn + 1);
        }
    }

    int minimumCost(vector <int> superior, vector <int> training) {
        for (int i = 0; i < MAX_N; i++) {
            G[i].clear();
        }

        S = superior; SN = S.size();
        T = training; TN = T.size();

        for (int i = 1; i < SN; i++) {
            G[S[i]].push_back(i);
        }

        sort(T.begin(), T.end());

        dfs(0);

        int res = INF;
        for (int i = 0; i < TN; i++) {
            res = min(res, dp[0][i]);
        }
        if (res == INF) res = -1;
        return res;
    }
};

// こっから最小費用流クラスの実装

const int MinCostFlow::INF = (int)1e9;

MinCostFlow::MinCostFlow(int vertexNumber) {
    m_vNum = vertexNumber;
    G = new vector<E>[vertexNumber];
    dist = new int[vertexNumber];
    prevv = new int[vertexNumber];
    preve = new int[vertexNumber];
}

MinCostFlow::~MinCostFlow() {
    delete[] G; G = 0;
    delete[] dist; dist = 0;
    delete[] prevv; prevv = 0;
    delete[] preve; preve = 0;
}

void MinCostFlow::addEdge(int v, int u, int cap, int cost) {
    G[v].push_back(E{ u, cap, cost, G[u].size() });
    G[u].push_back(E{ v, 0, -cost, G[v].size() - 1 });
}

int MinCostFlow::flow(int s, int t, int f) {
    int res = 0;
    while (0 < f) {
        for (int i = 0; i < m_vNum; i++) {
            dist[i] = INF;
        }
        dist[s] = 0;
        while (true) {
            bool update = false;
            for (int v = 0; v < m_vNum; v++) {
                for (int i = 0; i < G[v].size(); i++) {
                    if (G[v][i].cap <= 0) continue;
                    int to = G[v][i].to;
                    int cost = G[v][i].cost;
                    if (dist[v] + cost < dist[to]) {
                        dist[to] = dist[v] + cost;
                        prevv[to] = v;
                        preve[to] = i;
                        update = true;
                    }
                }
            }
            if (!update) break;
        }

        if (dist[t] == INF) {
            return INF;
        }

        int d = f;
        for (int cur = t; cur != s; cur = prevv[cur]) {
            d = min(d, G[prevv[cur]][preve[cur]].cap);
        }
        f -= d;
        res += dist[t] * d;

        for (int cur = t; cur != s; cur = prevv[cur]) {
            E& e = G[prevv[cur]][preve[cur]];
            e.cap -= d;
            G[cur][e.rev].cap += d;
        }
    }

    return res;
}