[문제 해결] P2014 수강신청(트리 DP+ 토폴로지)

제목: 현재 n개의 과목이 있고 각 과목은 일정한 가치가 있지만 과정은 한 개의 선행 과목이 필요할 수 있습니다. m개의 과목이 얻을 수 있는 가장 큰 가치를 물어보세요.분석: 처음에는 이 문제에 고리가 생길 수 있다고 생각했어요.(예를 들어 HAOI 2010 소프트웨어가 설치되어 있지만 Tarjan은 포기하려고 했지만 갑자기 토론반에서 어떤 사람이 이 문제에 고리가 없다고 힐끗 쳐다보았는데... 그래, 이렇게 하면 Easy를 비교할 수 있다. 우선 우리는 슈퍼 뿌리 노드로 숲을 한 그루로 연결한 다음에 토폴로지로 나무의 모든 잎 노드를 처리하고 한 층 한 층 추진해서 뿌리 노드가 처리될 때까지 해야 한다. PS: 반드시 기억해야 한다.m++, 뿌리 노드도 돈이 필요하니까!!!코드는 다음과 같습니다.

#include 
using namespace std;
struct node {
    int num;
    int fa;
    int son;
}p[400];
queue < int > q;
int f[400][400];
int n,m;
int main() {
    int i,j,k;
    scanf("%d%d",&n,&m);
    m++;
    p[0].fa=-1;
    for(i=1;i<=n;i++) {
        scanf("%d%d",&p[i].fa,&p[i].num);
        for(j=1;j<=m;j++)
            f[i][j]=p[i].num;
        p[p[i].fa].son++;
    }
    for(i=1;i<=n;i++)
        if(p[i].son==0)
            q.push(i);
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        int fa=p[x].fa;
        if(fa==-1) break;
        p[fa].son--;
        if(p[fa].son==0) {q.push(fa);}
        for(i=m;i>=0;i--) {
            for(j=i-1;j>=0;j--) {
                f[fa][i]=max(f[fa][i-j]+f[x][j],f[fa][i]);
            }
        }
    }
    printf("%d",f[0][m]);
    return 0;
}

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　by:Chlience

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[문제풀이] BZOJ 1010 장난감 포장 Toy

dp[j]+(f[i]−f[j]−c)2≤dp[k]+(f[i]−f[j]−c)2 d p [ j ] + ( f [ i ] − f [ j ] − c ) 2 ≤ d p [ k ] + ( f [ i ] − f [ j ] − c ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[문제 해결] P2014 수강신청(트리 DP+ 토폴로지)

좋은 웹페이지 즐겨찾기