题解：P4796 [BalticOI 2018] 路径

· · 题解

[BalticOI 2018] 路径题解

题意简述

找到长度至少为 2 的简单路径，使得路径上每个节点颜色各异，求满足长度小于等于 k 的方案数。

思路分析

发现 k \leq 5，不难结合题意得出搜索路径的长度不会比 k 更长。 显然有一个 O(n^2) 的搜素，对于每一个节点，通过栈模拟当前存在哪些颜色，扩展方案数即可。 核心代码如下。

bool check(int c)
{
    for(int i=1;i<=top;i++)
    {
        if(stk[i]==c) return 1;
    }
    return 0;
}
void DFS(int x,int lst,int dep,int f)
{
    if(dep>k) return ;
    for(int i=head[x];i;i=edge[i].next)
    {
        if(edge[i].to==lst) continue;
        if(check(col[edge[i].to])) continue;
        stk[++top]=col[edge[i].to];
        ans[f][dep+1]++;
        DFS(edge[i].to,x,dep+1,f);
        top--;
    }
    return ;
}

发现我们花了很多时间去找需要的颜色，并判断是否可行，优化这个部分。 对于 k 具有较偏小的限制，我们把颜色压缩成二进制数去判断。 对于单一的点，显然颜色判定可行，但最后判定答案需减去对应部分。 我们再处理出，对于每一个节点和他的邻居节点是否成为一条可行的链。 即设计状态 f_{i,j} 表示以 i 号节点为端点，压缩后颜色为 j 的方案数。

考虑状态如何转移

f_{x,(2^{col_x-1}) \oplus j} += f_{edge_i.to,j};

而对于无法转移的状态存在就是当前颜色数量不满足转移限制或者 2^{col_x-1}\cap j=0，转移方程右侧没有值也可以直接跳过。

具体实现

#include<iostream>
#include<map>
using namespace std;
struct Qi
{
    long long to;
    long long next;
}edge[600005];
long long head[300005],edge_cnt;
long long col[300005];
long long f[300005][35];
void add(long long u,long long v)
{
    edge_cnt++;
    edge[edge_cnt].to=v;
    edge[edge_cnt].next=head[u];
    head[u]=edge_cnt;
    return ;
}
long long cnt(long long x)
{
    long long res=0;
    while(x)
    {
        res+=(x&1);
        x>>=1;
    }
    return res;
}
int main()
{
    //freopen("path.in","r",stdin);
    //freopen("path.out","w",stdout);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>col[i];
        f[i][1<<col[i]-1]=1;
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
        if(col[u]!=col[v])
        {
            f[u][(1<<(col[u]-1))^(1<<(col[v]-1))]++;
            f[v][(1<<(col[u]-1))^(1<<(col[v]-1))]++;
        }
    }
    for(int c=3;c<=k;c++)
    {
        for(int x=1;x<=n;x++)
        {
            for(int i=head[x];i;i=edge[i].next)
            {
                for(int j=1;j<(1<<k);j++)
                {
                    if(((1<<(col[x]-1))&j)||cnt(j)!=c-1||f[edge[i].to][j]==0) continue;
                    f[x][(1<<(col[x]-1))^j]+=f[edge[i].to][j];
                }
            }
        }
    }
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<(1<<k);j++)
        {
            cout<<f[i][j]<<" ";
            sum+=f[i][j];
        }
        cout<<endl;
    }
    cout<<sum-n;
    return 0;
}

感觉和直接搜索存在很明显的差异，似乎主要体现在颜色的处理上，所以发现存在较小的值域限制时，不妨想到压缩状态。