[BZOJ4455] [ZJOI 2016] 작은 별 용척 원리 + 트리 DP

먼저 잘못된 DP,fi, j는 하위 트리 i에서 i가 j에 비치는 방안 수를 고려합니다. 그러면 한 점이 중복적으로 비치게 될 수 있습니다.우리는 다차원 상태fi, j, S가 매핑점이 대부분 S로 집합되는 방안을 고려하고 S를 매개로 DP를 하며 소박한 용척 원리로 정답을 구하면 된다.코드:

#include
#include
#include
#define ll long long
using namespace std;
int n,m,st[20],top;
ll f[20][20],ans;
bool mp[20][20];
struct edge
{
    int t;
    edge *next;
}*con[20];
void ins(int x,int y)
{
    edge *p=new edge;
    p->t=y;
    p->next=con[x];
    con[x]=p;
}
void dp(int v,int fa,int s)
{
    for(int i=1;i<=top;i++)  f[v][st[i]]=1;
        for(edge *p=con[v];p;p=p->next)
            if(p->t!=fa)
            {
                dp(p->t,v,s);
                for(int i=1;i<=top;i++)
                {
                    ll cal=0;
                        for(int j=1;j<=top;j++)
                            cal+=f[p->t][st[j]]*mp[st[i]][st[j]];
                    f[v][st[i]]*=cal;
                }
            }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        mp[x][y]=mp[y][x]=1;
    }
    for(int i=1;iint x,y;
        scanf("%d%d",&x,&y);
        ins(x,y);ins(y,x);
    }
    for(int s=0;s1<s++)
    {
        top=0;
        for(int i=0;iif((s>>i)&1) st[++top]=i+1;
        dp(1,0,s);
        for(int i=1;i<=top;i++)
            ans+=f[1][st[i]]*((n-top)&1?-1:1);  
    }
    printf("%lld",ans);
    return 0;
}

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

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

【경쟁 프로 전형적인 90문】008의 해설(python)

의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...

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

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

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다