Tim Pekerja

Soal#

Informasi#

• Sumber: CompFest 2012 - Final CPC Senior
• Tanggal: 2012-10-13 - 2012-10-14

Arsip#

• TLX

Ringkasan#

• Terdapat $N$ pekerja. Tiap pekerja memiliki peran antara mandor, kuli, atau sekretaris. Pekerja ke-$i$ juga memiliki tingkat kemampuan sebesar $X_i$.
• Terdapat pula $U$ ikatan pekerja. Ikatan pekerja ke-$j$ dinyatakan oleh tiga buah bilangan $A_j$, $B_j$, dan $Q_j$; yang berarti jika salah satu dari pekerja $A_j$ atau $B_j$ dijadikan anggota tim, maka pekerja yang satunya lagi juga harus dijadikan anggota tim. Penyatuan $A_j$ dan $B_j$ dalam tim akan menambahkan total kemampuan tim sebesar $Q_j$.
• Pak Chanek ingin membentuk tim pekerja yang terdiri atas tepat $K$ kuli, $M$ mandor, dan $S$ sekretaris. Bantulah Pak Chanek menentukan total kemampuan tim yang maksimum (yakni, total kemampuan pekerja + total kemampuan tambahan dari ikatan-ikatan pekerja).

Solusi#

Petunjuk#

Pembahasan#

Kita bisa pandang hubungan pekerja-pekerja dan ikatan-ikatan pekerja sebagai sebuah graf tidak berarah. Simpul (vertex) pada graf merupakan pekerja dan sisi (edge) pada graf merupakan ikatan pekerja. Setiap simpul $i$ memiliki nilai tingkat kemampuan sebesar $X_i$ dan tiap sisi $j$ memiliki "cost" sebesar $Q_j$. Graf akan memiliki setidaknya satu komponen (weakly connected component).

Untuk setiap komponen, kita harus menyimpan banyaknya kuli, mandor, dan sekretaris. Selain itu, kita juga menyimpan jumlahan $X_i$ untuk setiap simpul dan jumlahan $Q_j$ untuk setiap sisi pada tiap komponen, yang akan kita sebut sebagai value. Misal $C$ adalah suatu barisan yang mengandung semua komponen. Banyaknya kuli, mandor, dan sekretaris serta nilai value dari komponen ke-$n$ berturut-turut kita tandai dengan $c_{nk}$, $c_{nm}$, $c_{ns}$, dan $c_{nv}$.

Untuk menyelesaikan soal seluruhnya, kita dapat menggunakan solusi yang mirip dengan solusi dari permasalahan subset sum dan knapsack. Kita hanya perlu menambah dimensi dari kedua permasalahan tersebut.

Pertama, kita gunakan solusi dari permasalahan subset sum untuk mengecek apakah kita bisa membuat tim dengan jumlah pekerja yang tepat untuk tiap peran. Misal $f(n, k, m, s)$ menyatakan apakah kita bisa membentuk tim pekerja yang terdiri atas tepat $k$ kuli, $m$ mandor, dan $s$ sekretaris apabila kita menggunakan $n$ komponen pertama. $$ f(n, k, m, s) = \begin{cases} \textbf{true}, \\ \qquad \text{jika } n = k = m = s = 0 \\ \textbf{false}, \\ \qquad \text{jika } n = 0 \wedge (k \ne 0 \vee m \ne 0 \vee s \ne 0) \\ f(n - 1, k, m, s) \vee f(n - 1, k - c_{nk}, m - c_{nm}, s - c_{ns}), \\ \qquad \text{jika } c_{nk} \le k \wedge c_{nm} \le m \wedge c_{ns} \le s \\ f(n - 1, k, m, s), \\ \qquad \text{selain itu} \end{cases} $$

Kedua, kita gunakan solusi dari permasalahan knapsack untuk menentukan total kemampuan tim yang maksimum. Misal $g(n, k, m, s)$ menyatakan total kemampuan maksimum dari tim yang terdiri atas tepat $k$ kuli, $m$ mandor, dan $s$ sekretaris apabila kita menggunakan $n$ komponen pertama. $$ g(n, k, m, s) = \begin{cases} 0, \\ \qquad \text{jika } n = k = m = s = 0 \\ -\infty, \\ \qquad \text{ jika } n = 0 \wedge (k \ne 0 \vee m \ne 0 \vee s \ne 0) \\ \max(g(n - 1, k, m, s), g(n - 1, k - c_{nk}, m - c_{nm}, s - c_{ns}) + c_{nv}), \\ \qquad \text{ jika } c_{nk} \le k \wedge c_{nm} \le m \wedge c_{ns} \le s \wedge f(n, k, m, s) = \textbf{true} \\ g(n - 1, k, m, s), \\ \qquad \text{ selain itu} \end{cases} $$

Jawaban akhir dari soal ini adalah nilai dari $g(|C|, K, M, S)$.

Kode#

#include <iostream>
#include <vector>
using namespace std;
typedef long long int lli;
typedef pair <int, lli> pil;

const lli INF = 1E15;

struct component {
    int role[3];
    lli cost;

    component(){
        cost = 0;
        fill(role, role + 3, 0);
    }
};

lli workers_cost, union_cost;
pil workers[100];
vector <pil> al[100];
vector <component> graph;
bool vis[100];
lli dp[101][16][16][16];
bool subset_sum[101][16][16][16];

void dfs(int u){
    if(!vis[u]){
        vis[u] = 1;
        graph.back().role[workers[u].first]++;
        workers_cost += workers[u].second;
        for(const pil& p : al[u]){
            const int& v = p.first;
            union_cost += p.second;
            dfs(v);
        }
    }
}

int main(){
    int T;
    cin >> T;
    while(T--){
        int N, P, K, M, S;
        cin >> N >> P >> K >> M >> S;
        graph.clear();
        for(int i = 0; i < N; i++){
            vis[i] = 0;
            al[i].clear();
        }

        for(int i = 0; i < N; i++){
            string role;
            cin >> role >> workers[i].second;
            if(role == "kuli") workers[i].first = 0;
            if(role == "mandor") workers[i].first = 1;
            if(role == "sekretaris") workers[i].first = 2;
        }

        for(int i = 0; i < P; i++){
            int Ai, Bi;
            lli Qi;
            cin >> Ai >> Bi >> Qi;
            Ai--; Bi--;
            al[Ai].push_back({Bi, Qi});
            al[Bi].push_back({Ai, Qi});
        }

        graph.push_back(component());
        for(int i = 0; i < N; i++){
            if(!vis[i]){
                workers_cost = union_cost = 0;
                graph.push_back(component());
                dfs(i);
                graph.back().cost = workers_cost + union_cost/2;
            }
        }

        for(size_t n = 0; n < graph.size(); n++){
            for(int k = 0; k <= K; k++){
                for(int m = 0; m <= M; m++){
                    for(int s = 0; s <= S; s++){
                        dp[n][k][m][s] = -INF;
                        subset_sum[n][k][m][s] = false;
                    }
                }
            }
        }
        subset_sum[0][0][0][0] = true;
        dp[0][0][0][0] = 0;

        for(size_t n = 1; n < graph.size(); n++){
            for(int k = 0; k <= K; k++){
                for(int m = 0; m <= M; m++){
                    for(int s = 0; s <= S; s++){
                        dp[n][k][m][s] = dp[n - 1][k][m][s];
                        subset_sum[n][k][m][s] = subset_sum[n - 1][k][m][s];

                        if(graph[n].role[0] <= k && graph[n].role[1] <= m && graph[n].role[2] <= s){
                            int nx_k = k - graph[n].role[0];
                            int nx_m = m - graph[n].role[1];
                            int nx_s = s - graph[n].role[2];

                            if(subset_sum[n - 1][nx_k][nx_m][nx_s]){
                                subset_sum[n][k][m][s] = true;
                                lli nx_cost = dp[n - 1][nx_k][nx_m][nx_s] + graph[n].cost;
                                dp[n][k][m][s] = max(dp[n][k][m][s], nx_cost);
                            }
                        }
                    }
                }
            }
        }

        if(!subset_sum[graph.size() - 1][K][M][S])
            cout << "tidak mungkin\n";
        else
            cout << dp[graph.size() - 1][K][M][S] << '\n';
    }
    return 0;
}