A simple Blog for wyx I've been down the bottle hoping.
4455: [Zjoi2016]小星星 状压dp + 容斥原理 枚举
发表于: | 分类: Oi | 评论:0 | 阅读:128

开始的时候根本不会啊……ZJ的题实在是太神了Orz

首先$n\le 17$相信任何一个有$Oi$常识的人都知道他考得是什么算法

现在我们需要思考的就是状压到底压点什么,根据暴(题)力(解)的经验,我们可以先不考虑这个嘛……

我们先考虑如果不考虑每个点只被影射一次这个限制改怎么做……显然是可以$dp$计数的嘛,$f(i,j)$表示i节点为$j$颜色的时候方案数

那么显然是有转移方程的么

$$f(i,j) = \prod g(son), g(son) = \sum\limits_{m=1}^{tot}{f(son,m)\times map(a_j,a_m)}$$

然后……然后你暴力枚举一下所有可选点集的情况容斥一下就行了

所以没有真的状压……只是枚举了状态Orz

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

const int N = 50+5;
const int M = N << 1;
int n, m, tot;

int head[N];

struct graph {
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)  {
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y); head[x] = cnt;
    edge[++cnt] = graph(head[y],x); head[y] = cnt;
}

LL F[N][N];
int a[N];

bool mp[N][N];

inline void DFS(int x,int fa) {
    for(int i=head[x];i;i=edge[i].next) {
        if(edge[i].to != fa) {
            DFS(edge[i].to,x);
        }
    }
    for(int i=1;i<=tot;++i) F[x][i] = 1;
    for(int i=head[x];i;i=edge[i].next)if(edge[i].to != fa) {
        for(int j=1;j<=tot;++j) {
            LL tmp = 1;
            for(int k=1;k<=tot;++k) 
                if(mp[a[j]][a[k]]) tmp += F[edge[i].to][k];
            F[x][j] *= tmp;
        }
    }
}

int main() {
    n = read(), m = read(); int x, y;
    for(int i=1;i<=m;++i) x = read(), y = read(), mp[x][y] = mp[y][x] = 1;
    for(int i=1;i<n;++i) x = read(), y = read(), add(x,y);
    int Max = (1<<n) - 1;  
    LL ans = 0;
    for(int i=1;i<=Max;++i) {
        LL now = 0; tot = 0;
        for(int j=1;j<=n;++j) if((1<<(j-1))&i) a[++tot] = j;
        DFS(1,-1); for(int j=1;j<=tot;++j) now += F[1][j];
        if((tot&1)== (n&1)) ans += now;
        else ans -= now;
    }
    cout << ans << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP