백준 1005 ACM Craft

www.acmicpc.net/problem/1005

1005번: ACM Craft

이 문제는 알고리즘 & 자료구조 카테고리에 기록한 이전 포스팅을 반드시 참조하기 바란다. 건물을 짓는 순서들은 모두 모아 사이클이 없는 단방향 그래프로 구성해 볼 수 있다. 위상정렬 후에 앞에서부터 건설 시간을 넘겨주면 된다. 그리고 각 정점에서는 부모 정점에서 내려오는 값들 중 최댓값만 취하여 갱신해주면 된다. 그렇게 목표 건물까지 누적하면 답을 구할 수 있다

 

<주요 내용>

위상정렬, DP

 

<코드>

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;
const int sz=1e3+1;
int a,b,t,n,k,w,btime[sz],indegree[sz],cost[sz];
vector<int>graph[sz],toporder;
queue<int>q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>t;
    while(t--){
        memset(indegree,0,sizeof(indegree));
        memset(cost,0,sizeof(cost));
        vector<int>graph[sz],toporder;
        queue<int>q;
        cin>>n>>k;
        for(int i=1;i<=n;++i)cin>>btime[i];
        while(k--){
            cin>>a>>b;
            graph[a].push_back(b);
            indegree[b]++;
        }
        cin>>w;

        for(int i=1;i<=n;++i)if(!indegree[i])q.push(i);
        while(!q.empty()){
            auto curr=q.front();q.pop();
            toporder.push_back(curr);
            for(auto nx:graph[curr])if(!--indegree[nx])q.push(nx);
        }
        for(int i=0;i<n;++i){
            auto curr=toporder[i];
            cost[curr]+=btime[curr];
            for(auto nx:graph[curr]){
                cost[nx]=max(cost[nx],cost[curr]);
            }
        }
        cout<<cost[w]<<endl;
    }
    return 0;
}

 

for(auto nx:graph[curr])if(!--indegree[nx])q.push(nx);

위와 같이, !--indegree[nx]를 통해 indegree값이 0이 되었는지를 체크할 수 있다. 그리고 0이 되었다면 큐에 담아주면 된다.