글 읽기 - cpp 54%에서 계속 틀리네요.

bigbell999 1년 전 0

복잡하게 시도했습니다;

간단히 설명드리면 위상정렬로 각 건물들의 테크 레벨을 정하고 (ex: 처음부터 진입차수가 0이면 테크레벨 = 1)

각 테크 레벨마다 가장 건설 시간이 길며, w를 건설하는데 필요한 건물들의 건설시간 합을 답으로 냈습니다.

w를 건설하기위해 필요한 건물을 판단하는 데에는 w에서 부터 시작하는 bfs를 실행했습니다; (그래프 간선방향을 반대로 하여서)

그래도 54%에서 틀리네요;; 반례라도 찾아주시면 다시 한번 생각해보겠습니다.

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

int main()
{
    int t, n, m;
    
    cin >> t;
    
    for (int k=0; k<t; k++)
    {
        //input
        cin >> n >> m;
        
        //건물 건설시간
        vector<int> demand;
        demand.resize(n+1, 0);
        
        //인접리스트
        vector<int> adj[1001];
        
        //for bfs & answering.
        vector<int> radj[1001]; // 역 인접리스트.
        vector<int> is_on_b2w;
        is_on_b2w.resize(n+1);
        
        //건물의 테크단계
        vector<int> tech;
        tech.resize(n+1, 0);
        
        //진입차수.
        vector<int> in_d;
        in_d.resize(n+1, 0);
        
        //같은 테크 건물들의 건설시간.
        vector<int> tech_time[1001];
        
        //queue for toplogy sorting.
        queue<int> q;
        
        //input
        for (int i=1; i<=n; i++) cin >> demand[i];
    
        for (int i=0; i<m; i++)
        {
            int a, b;
            cin >> a >> b;
        
            adj[a].push_back(b);
            radj[b].push_back(a);
            in_d[b]++;
        }
        
        //지으면 이기는 건물의 번호.
        int build_2_win;
        cin >> build_2_win;
        
        //solve
        for (int i=1; i<=n; i++)
        {
            if (in_d[i] == 0) 
            {
                q.push(i);
                tech[i] = 1;
            }
        }
    
        while( !q.empty() )
        {
            int cur = q.front();
            q.pop();
        
            for (int i=0; i< adj[cur].size(); i++)
            { 
                int nxt = adj[cur][i];
                if (--in_d[nxt] == 0) 
                {
                    q.push(nxt);
                    tech[nxt] = tech[cur] + 1;
                }
            }
        } 
        
        //bfs
        q.push(build_2_win); is_on_b2w[build_2_win] = 1;
        while(!q.empty())
        {
            int x = q.front(); q.pop();
            
            for (int nx : radj[x])
            {
                if (!is_on_b2w[nx])
                {
                    q.push(nx);
                    is_on_b2w[nx] = 1;
                }
            }
        }
        
        int tech_2_win = tech[build_2_win];
        
        for (int i=1; i<=n; i++) 
        {
            if ( tech[i] < tech_2_win && is_on_b2w[i] ) tech_time[tech[i]].push_back( demand[i] );
        }
        
        long long res = 0;
        
        for (int i=1; i<tech_2_win; i++)
        {
            int max = 0;
            for (int j=0; j<tech_time[i].size(); j++)
            {
                if ( tech_time[i][j] > max ) max = tech_time[i][j];
            }
            res += max;
        }
        
        res += demand[build_2_win];
        
        cout << res << '\n';
    }
    
    return 0;
}

osthus 1년 전 15

각 테크 레벨마다 건설 시간이 가장 긴 건물의 건설 시간을 더하는 것이 최소 건설 시간을 보장하지 않습니다.

1
6 6
10 5 1 1 9 8
1 2
1 4
2 3
4 5
3 6
5 6
6
    
// 출력: 32
// 정답: 28

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

cpp 54%에서 계속 틀리네요.

bigbell999 1년 전 0

osthus 1년 전 15

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말