题目相关

题目链接：P4796 [BalticOI 2018]路径

题目描述：

给定一张 $N$ 个点 $M$ 条边的无向图，每个点有一个颜色，所有点的颜色共有 $K$ 种，编号为 $1\ldots K$。求图上有多少条长度至少为 $2$ 的简单路径，满足路径上的每一个点的颜色互不相同。
路径上的点的连接顺序不同看作不同的两条路径。

输入输出格式：

输入格式：
第一行包含三个整数 $N$, $M$ 和 $K$。
第二行包含 $N$ 个在 $1$ 到 $K$ 之间的整数，表示每个点的颜色。
接下来的 $M$ 行每行两个整数 $a$ 和 $b$，表示图的一条边。
数据保证图无自环无重边。
输出格式：
输出一个整数表示每一个点颜色都不同的路径条数。保证答案不会超过 $10^{18}$。

输入输出样例：

输入	输出
4 3 3 1 2 1 3 1 2 2 3 4 2	10
9 11 4 1 2 3 4 1 2 1 2 2 1 2 1 3 2 3 2 4 3 6 6 2 6 5 4 3 4 5 7 8 9 8	70

说明/提示：

样例 1 解释：

样例 1 中表达的图如上图所示。每个点的底色分别为白色（颜色 $1$）、灰色（颜色 $2$）或黑色（颜色 $3$）。共有 $10$ 条路径满足路径上的所有点的颜色都不同。它们是：1-2, 2-1, 2-3, 3-2, 2-4, 4-2, 1-2-4, 4-2-1, 3-2-4 和 4-2-3。

注意 1 不能看作是一条路径，因为一条路径至少连接两个点。1-2-3 也不满足条件，因为有两个点都是 $1$ 号颜色。

数据范围：

子任务	分值	数据范围
$1$	$23$	$1\le N,M\le 100,1\le K\le 4$
$2$	$20$	$1\le N,M\le 300\ 000,1\le K\le 3$
$3$	$27$	$1\le N,M\le 300\ 000,1\le K\le 4$
$4$	$30$	$1\le N,M\le 100\ 000,1\le K\le 5$

博主乱搞

蒟蒻解析：

发现 $k$ 的范围很小，理所当然地想到状态压缩了。我们考虑如何统计答案。
按照常规思路，我们一般选择从某个点开始，枚举他的状态，进行答案更新。但可能不太好实现，如：

我们从图易知关于 1,2,3 的贡献是离不开剩下两个点的。但是肯定有一个初始出发点，使得其他点的情况没有得到遍历，导致答案减少。
我们换一种思路，从小到大枚举状态确定时的该点的贡献；这样子就避免了这个问题。转移方程：$f[v][s|color[v]]=\sum f[u][s]$

蒟蒻代码：

cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long 
#define il inline
const int maxn=300010;
vector<int> G[maxn];
int n,m,k,ru,rv;
int col[maxn];
int s[(1<<5)+5],stot;
ll f[maxn][(1<<5)+5];
ll ans;
inline int bt(const int &x){
    int tmp=1,tot=0;
    while (tmp<=x){
        if (tmp&x) ++tot;
        tmp<<=1;
    }
    return tot;
}
bool cmp(const int &a,const int &b){
    int ta=bt(a),tb=bt(b);
    return (ta==tb)?a<b:ta<tb;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=(1<<k);++i){
        s[i]=i;
    }
    stot=(1<<k)-1;
    sort(s+1,s+1+stot,cmp);
    for (int i=1;i<=n;++i){
        scanf("%d",&col[i]); col[i]--;
    }
    for (int i=1;i<=m;++i){
        scanf("%d%d",&ru,&rv);
        G[ru].push_back(rv);
        G[rv].push_back(ru);
    }
    for (int i=1;i<=n;++i){
        f[i][1<<(col[i])]=1;
    }
    for (int i=1;i<=stot;++i){
        for (int j=1;j<=n;++j){
            if (f[j][s[i]]){
                if (i>k) ans+=f[j][s[i]];
                for (int l=0;l<G[j].size();++l){
                    int to=G[j][l];
                    if (1<<(col[to])&s[i]) continue;
                    f[to][s[i]|(1<<(col[to]))]+=f[j][s[i]];
                }
            }
        }
    }
    printf("%lld",ans);
    return 0;
}