# 【ZeroJudge】 k734. Open Treasure Box

## [題目連結](https://zerojudge.tw/ShowProblem?problemid=k734)

## **時間複雜度**

* $O(KN)$

## **解題想法**

有 $N$ 個寶盒編號與 $m$ 種鑰匙。一開始你有某些鑰匙。每個寶盒需要 $k$ 支鑰匙才能開啟，每開啟一個寶盒可以獲得指定的 $k$ 支鑰匙。計算一共能開啟多少個寶盒。

基本上，這題需要的就是執行以下的步驟：

1. 紀錄擁有的鑰匙
2. 重複以下步驟，直到沒有新的鑰匙：
    檢查擁有的鑰匙可以開啟那些寶盒 ➡ 若有寶盒可以開啟，則開啟並獲得該寶盒內的鑰匙

### 分析樸素作法

1. 每次都重複檢查所有的寶盒，但是這樣時間複雜度 $O(N^2)$ 會太高
2. 如果我們把已經開啟的寶盒丟棄，下次不再檢查，那會稍微改善，但還是不夠好。因為在最壞的狀況下，每次都只開啟一個新的寶盒，那麼要檢查的寶盒次數就會是 $O(N^2)$

\begin{aligned}
O(N^2) Proof：\quad n+ (n-1) + (n-2) + (n-3) + \cdots + 1 =\sum_{i=1}^n i = O(N^2)
\end{aligned}

### AC 作法

給予每一個寶盒和一個鑰匙一個倒數計數器 $indegree$。對於每個寶盒，紀錄該寶盒還需要多少支鑰匙才能開啟，於每一支鑰匙，記錄它可以用在哪些寶盒的開啟上。

每當獲得一支新鑰匙時，將它可以開啟的寶盒 $indegree$ 減一，若此時 $indegree$ 歸 0，則得到一個新開啟的寶盒。如此一來，對於每支新獲得的鑰匙，我們只要花該鑰匙所開啟寶盒數的時間就可以完成檢查，因為每個鑰匙可開啟的寶盒總數等於所有寶盒需求鑰匙的總數，也就是 $KN$，所以檢查盒子開啟的總時間就是 $O(KN)$

最後值得注意的是，因為鑰匙會有重複的，這裡我們還需要避免重複檢查相同的鑰匙，我們可以用一個陣列 $visited$ 紀錄哪些鑰匙已經處理過了。

## **完整程式**

/* Question : ZJ k734. Open Treasure Box */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int MAXN = 1e5 + 50;
const int Mod = 1e9 + 7;
int n, m, k, t, key, box, tmp, res;
vector<vector< int > > graph;
vector<int> todo;
int indegree[MAXN];
bool visited[MAXN * 2];

signed main(){
    opt;
    cin >> n >> m >> k >> t;
    graph.resize( n + m + 5 );
    for( int i = 0 ; i < t ; i++ ){
        cin >> key;
        todo.push_back(key+n);
    }

    for( int i = 0 ; i < n ; i++ ){
        for( int j = 0 ; j < k ; j++ ){
            cin >> tmp;
            graph[tmp+n].push_back(i);
        }
    }

    for( int i = 0 ; i < n ; i++ ){
        for( int j = 0 ; j < k ; j++ ){
            cin >> tmp;
            graph[i].push_back(tmp+n);
            indegree[i]++;
        }
    }

    res = 0;
    while( !todo.empty() ){
        int ctn = todo.back();
        todo.pop_back();
        if( visited[ctn] ) continue;
        visited[ctn] = true;
        for( auto i : graph[ctn] ){
            if( ctn < n ){
                todo.push_back(i);
            }else{
                indegree[i]--;
                if( indegree[i] == 0 ){
                    todo.push_back(i);
                    res++;
                }
            }
        }
    }

    cout << res << "\n";
}