글 읽기 - 1967 반례나 지적 부탁드립니다.

kopasd99 2년 전 1

안녕하세요 3시간째 73퍼에서 막힌 사람입니다. 당연히 질문에 있는 반례들은 모두 통과했고요..

코드를 설명해보자면, 인접 리스트로 트리를 만들고, 2차원 배열로 가중치를 적어뒀습니다.

만*만*4(int)=4억비트=400MB로 크기 에러가 나니, unsigned char을 사용해서 100MB만 사용, 실제로 메모리 초과때문에 틀린것 같지는 않습니다.

그리고 트리의 자식 노드가 2개 이상인 것들을 head 에 저장, 이 것들을 모두 DFS로 돌려서, 각 각 자식 노드가 하나씩 DFS되게 run 함수와 run2 함수를 따로 만들어, 각각 자식들의 가중치를 따로 계산해, priority_queue에 넣어넣고, 가장 큰것 2개만 뽑아서 더한뒤, ans변수에 넣었고, 이를 반복해서 가장 큰 가중치를 계산할 수 있었습니다.

고수님들 무엇이 문제인지 도와주시면 감사하겠습니다!!! 또한 코린이라 이것저것 지적해주시면 너무나 감사하겠습니다.

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

vector<int> map[10001];
vector<int> head;
priority_queue<int> maxValues;
unsigned char weight[10001][10001];

int maxValue=0;
int ans=0;

void run2(int now,int max)
{
    if(max>maxValue)maxValue=max;
    for(int i=0;i<map[now].size();i++)
    {
        run2(map[now][i],max+weight[now][map[now][i]]);
    }
}

void run(int now,int max)
{
    for(int i=0;i<map[now].size();i++)
    {
        run2(map[now][i],max+weight[now][map[now][i]]);
        maxValues.push(maxValue);
        maxValue=0;
    }
    int x=0;
    if(maxValues.size()>1)
    {
        x+=maxValues.top();
        maxValues.pop();
        x+=maxValues.top();
        maxValues.pop();
        if(x>ans)ans=x;
    }
    else ans+=maxValues.top();
    
}

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

    int n,a,b,c,max=0;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        if(a>max)max=a;
        map[a].push_back(b);
        weight[a][b]=c;
    }
    for(int i=0;i<=max;i++){ if(map[i].size()>=2){ head.push_back(i); } }//간선이 나뉘는 것들

    if(head.empty())//간선이 나뉘지 않고 수직 형태로 이어지는 트리일 경우
    {
        for(int i=0;i<=max;i++)
        {
            if(map[i].size()>0)
            {
                run(i,0);
                break;
            }
        }
    }

    vector<int>::iterator iter;
    for(iter=head.begin();iter!=head.end();iter++)
    {
        run(*iter,0);
        priority_queue<int> empty;
        swap(maxValues,empty);

    }

    printf("%d",ans);
}

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