题解P1078【文化之旅】

· · 个人记录

首先替CCF申冤：为什么这是错题？？？

这道题完全有正确做法！

我写的这个，估计算是半个正解了。

------------------申冤完毕，分割线-------------------

下面我讲讲我的方法：

考虑：本题 n \le 100,k \le 100 ，理论上状态总数有 n\times 2^k 种，存不下，搜索剪枝也很难不 TLE 。

所以首先要解决的问题是：如何将这些状态都存下？

我们学过 hash ，知道很大的数也能被压在一段内储存。

于是我们发扬下去这种思想，每个文化学习情况，都对应着一个值。

对应方法：将文化的学习情况用二进制表达，因为 k \le 100 ，所以可以用 __int128 存储，然后再取模一个数 luck。

对于那个数 luck 的选择，不能过大，因为要保证 n\times luck 不爆空间。还要保证跑 dijkstra 的时间不会爆。

dijkstra本身复杂度是 O(m\log m) ，但因为每个点都拆成了 luck 种情况，所以这里 m=m\times luck 。

所以要保证 O(m\times luck\times \log (m\times luck)) 不 TLE 。

算一算，luck 最大也就是 10^2 左右，再大肯定爆时间。虽然上面复杂度一定跑不满，但时间也很可观了。

于是再一想：我们平常 hash 一般都用延后储存或链表式来做，但是都建立在存储个数不多的情况之上。

问题来了：文化情况应该非常多，能完全用它保存吗？估计不行！

怎么办？

我们可以认为如果两个文化情况 \bmod \ luck 所得值相同，但其本身不同的情况，那就是相同的！

说完这句话，大家是不是疑惑了：“本身不同怎么能认为相同呢？这样如果知道 luck 就很容易造一组数据 hack 掉啊！”

所以，我们从上面说的话中找找想法：如果不知道 luck 会怎样呢？

请出我们的救星——（瞎搞）随机化算法：

我们可以定义好多个 luck ，让它跑个几遍十几遍的……

问题是：这些答案可能不同，如何合并？

因为上面提到的方法本质上是随机剪枝，得出的答案一定 \ge ans，所以取所有情况的最小值即可。

dijkstra 的改动：

1.用 vis 数组记忆化，第一维点，第二维文化 \bmod \ luck 。

2.用 priority_queue 记录时，记录点、距离和文化情况(注意不是 \bmod \ luck 以后的值，要不然判断文化冲突就难办了)。

3.文化判重用当前文化值 &（与运算） 另一端的文化。

4.文化判断排斥：输入 k\times k 的矩阵时预处理出每种文化对其他文化的排斥情况，处理成二进制，位运算求解（可以参考代码）。

5.最优性剪枝：我们跑完第一次得到了答案 ans ，用它来做最优性剪枝。

6.正确性优化：由于之前已经限定了总状态数，那么我们可以用一个 map 来将所有的 (x,c) (x是点编号，c是文化)，都映射到一个 int 数组进行保存。

检测到一个位置如果来过，而且原来存着的数更小，那说明这个 luck 之前存在错误剪枝，我们将当前值改为原来存着的值即可修正。

同理，如果一个位置存着的数偏大，那说明前几次有错误剪枝，将存着的数改正。

时间复杂度与正确性分析：

设检验 T 次，luck 选在 50 左右最为合适，时间复杂度为稳定的 O(Tmluck\times \log(mluck)) 。

还有一点注意：因最优性剪枝之后肯定跑得很快，所以复杂度的大头都集中在第一次。所以可以适当地调小第一次的 luck 。

实际上其他题解中写到“不管文化跑一次”，其实就是第一个 luck 为 1 的情况

实测速度比想象的要快不少。

正确性：不太好讲，但应该不低。

本身就是选择最优路径，某个点因为文化情况而选择较劣路径本身就是小概率事件，正好被 10 次剪枝都剪掉的概率就更小了，几乎可以忽略了。

如果有大佬能明确算出最坏情况正确率，希望您能提出您宝贵的见解。

luogu 数据确实比较水， T=1 都能 AC 。

贴上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=115,inf=0x3f3f3f3f;
const int mod[N]={7,31,37,41,43,47,53,59,61,67},T=10;//验10次
int now,ans=inf;
int n,m,k,s,t,cul[N],dis[N][N],vis[N][N];
__int128 no[N];
struct nd{int v,w;};
vector <nd> g[N];
struct nd2
{
    int x,dis;
    __int128 cul;
    bool operator <(const nd2 &b) const
    {
        return dis>b.dis;
    }
};
struct nd3
{
    int x;__int128 cul;
    bool operator <(const nd3 &b) const
    {
        return x<b.x||x==b.x&&cul<b.cul;
    }
};
map <nd3,int> M;
int cnt=0,dd[10000005];
void bfs()
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue <nd2> q;
    q.push((nd2){s,0,(__int128)1<<cul[s]-1});
    while(!q.empty())
    {
        nd2 tt=q.top();q.pop();
        int x=tt.x,d=tt.dis;
        __int128 c=tt.cul;
        if(vis[x][(int)(c%mod[now])]) continue;
        vis[x][(int)(c%mod[now])]=1;
        if(x==t) {ans=min(ans,d);return;}
        if(d>=ans) continue;
        nd3 t1=(nd3){x,c};
        if(M.count(t1)==1)
        {
            int pos=M[t1];
            if(dd[pos]<=d) d=dd[pos];//错误剪枝
            else dd[pos]=d;
        }
        else M[t1]=++cnt,dd[cnt]=d;

        dis[x][(int)(c%mod[now])]=d;
        for(int i=0;i<g[x].size();i++)
        {
            int v=g[x][i].v,w=g[x][i].w;
            if((c&no[cul[v]])!=0) continue;
            __int128 c1=(__int128)1<<cul[v]-1;
            if((c&c1)!=0) continue;
            if(vis[v][(int)((c|c1)%mod[now])]) continue;
            q.push((nd2){v,d+w,c|c1});
        }
    }
}
int main()
{
    scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
    for(int i=1;i<=n;i++) scanf("%d",&cul[i]);
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
        {
            int x;
            scanf("%d",&x);
            no[i]+=(__int128)x<<j-1;
        }
    for(int i=1;i<=m;i++)
    {
        int x,y,d;
        scanf("%d%d%d",&x,&y,&d);
        g[x].push_back((nd){y,d});
        g[y].push_back((nd){x,d});
    }
    for(now=0;now<T;now++) bfs();
    if(ans>1000000000) printf("-1\n");
    else printf("%d\n",ans);
}

我这算是靠谱的多项式复杂度的算法吗？是的（至少我这么觉得）。

如果不信可以看这个。