srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ABC 026 C - 高橋君の給料

問題

問題概要

省略

解法

上司から直属の部下に対して辺を張り、有向グラフを作成する。それを利用して、dfsを行う。部下がいないとき、つまり、グラフ上で葉の部分に該当する部下の給料は1なので、1を返す。部下が存在するとき、つまり、葉以外の頂点では、子の給料の最大値と最小値を計算して、最大値+最小値+1をかえせばよい。これを再帰関数で実装すればいい。
またループで解く方法もあり、数字の大きい人ほど、グラフ上で表したときに下側にいるので、ループを番号が大きい人から回すようにすればできる。

ミス

なし。

コード

再帰関数

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
int n;
vector<int> G[22];

int dfs(int u){
    int ma = 0, mi = INF;
    if(G[u].size() == 0){//葉
        return 1;
    }

    for(auto v : G[u]){
        ma = max(ma, dfs(v));
        mi = min(mi, dfs(v));
    }
    return ma + mi + 1;
}

int main(void){
    cin >> n;
    for (int i = 1; i < n; ++i){
        int b; cin >> b; b--;
        //b -> i
        G[b].push_back(i);
    }
    printf("%d\n", dfs(0));
    return 0;
}

ループで実装した場合

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
int n;
vector<int> G[22];

int main(void){
    cin >> n;
    for (int i = 1; i < n; ++i){
        int b; cin >> b; b--;
        //b -> i
        G[b].push_back(i);
    }
    
    int dp[20];//dp[i] := i番目の社員の給料
    //もらうdp
    for (int u = n - 1; u >= 0; --u){
        if(G[u].size() == 0){
            dp[u] = 1; continue;
        }
        int ma = 0, mi = INF;
        for(auto v : G[u]){
            ma = max(ma, dp[v]);
            mi = min(mi, dp[v]);
        }
        dp[u] = ma + mi + 1;
    }
    printf("%d\n", dp[0]);
    return 0;
}