글 읽기 - [C++] 트리의 독립집합 반례가 뭐가있는지 모르겠습니다

gi5005 3년 전 0

일단 기본적으로 게시판 예제는 정상작동하는데 뭐가문제인지 모르겠습니다

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include<stack>

#define MAX 10001
using namespace std;
int dp[MAX][2]; // first : 포함하려는 노드 second 1 == 포함 0 == 미포함

vector<int> E[MAX];
int arr[MAX];
bool vst[MAX];
int N;
void dfs(int curNode, int num)
{
    if (num > N+1)
    {
        return ;
    }
    vst[curNode]=true;
    dp[curNode][1] = arr[curNode];
    dp[curNode][0] = 0;    
    for(int i=0;i<E[curNode].size();i++)
    {
        int nextNode = E[curNode][i];
        if(nextNode == curNode){continue;}
        if(!vst[nextNode])
        {
            dfs(nextNode,num+1);
            dp[curNode][0] += max(dp[nextNode][1],dp[nextNode][0]);//현제노드 미포함 
            dp[curNode][1] += dp[nextNode][0]; 
        }
    }
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }
    while (cin.eof() == false)
    {
        int node1, node2;
        cin >> node1 >> node2;
        E[node1].push_back(node2);
        E[node2].push_back(node1);
    }
    int root[2];
    memset(vst,false,sizeof(vst));
    dfs(1, 1);
    cout << max(dp[1][0],dp[1][1])<<"\n";
    
    //tracing
    vector<int> tmp;
    stack<int> st;
    bool isCheck=false;
    for(int i=N;i>=1;i--)
    {
        if(isCheck)
        {
            isCheck = false;
            continue;
        }
        if(dp[i][0]<dp[i][1])
        {
            isCheck = true;
            st.push(i);
        }
        else
        {
            isCheck=false;
        }
    }
    while(!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
    //for(int i=1;i<=N;i++)
    //{
        //cout  << "dp["<<i<<"][0]" <<  dp[i][0] << "\n";
        //cout  << "dp["<<i<<"][1]" <<  dp[i][1] << "\n";
    //}
}

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

문제

문제

출처

ICPC

[C++] 트리의 독립집합 반례가 뭐가있는지 모르겠습니다

gi5005 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말