题解 P6622 【[2020 年联考 A 卷] 信号传递【暂无数据】】

· · 题解

upd: 补充代码

设 x 所在的位置为 p_x，那么如果存在一次信号传递为：x\rightarrow y，花费代价为：

\begin{cases}p_y-p_x&p_x<p_y\\k(p_x+p_y)&p_x>p_y\end{cases}

设 f_S 表示当前已经用 S 中的信号站填上了 1\sim|S| 这些位置，那么转移时已知当前信号站的位置和这个信号站与其他信号站的相对大小关系。

预处理 e_{x,y} 表示 x 到 y 的信号传递次数后，就可以 O(m) 地计算新加入的信号站对答案的贡献：

f_{S}=\min_{x\in S}\{{f_{S-x}+|S|\sum_{i\in S-x}(ke_{x,i}+e_{i,x})+|S|\sum_{i\notin S}(ke_{i,x}-e_{x,i})\}}

因为转移共有 m2^m 次，所以时间复杂度为 O(m^22^m)。

进一步观察转移的式子，可以发现转移中 p_x（在上式中等于 |S|） 的系数取决于 S 与 x 间入边和出边的数量。

因此，设 to_{S,x} 表示在转移 f_{S}\rightarrow f_{S+x} 中 p_x 的系数，则 to_{S+x,y} 可以在已知 to_{S,y} 的情况下 O(1) 计算出来：

to_{S+x,y}=to_{S,y}+(1-k)e_{x,y}+(1+k)e_{y,x}

这样就得到了一个时空复杂度均为 O(m2^m) 的算法。

但是空间复杂度过高，需要继续优化。

观察到转移的时候只会从 1 个数较少的状态转移到较大的状态，因此可以按 1 的个数进行滚动数组优化，空间复杂度就降至 O(2^m+m\binom{m}{m/2})，可以通过本题。

#include<bits/stdc++.h>
using namespace std;
#define V inline void
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=23,M=14e5,INF=0x7fffffff;
int n,m,k,S,cnt,tot,f[1<<N];
int e[N][N],to[2][M][N],w[2][M];
V add_edge(int x,int y){if(x!=y&&x)e[x-1][y-1]++;}
V input(){
    scanf("%d%d%d",&n,&m,&k),(S=1<<m)--;
    for(int x=0,y;n--;add_edge(x,y),x=y)scanf("%d",&y);
}
V init(){
    FOR(i,1,S)f[i]=INF;
    FOR(i,0,m-1)FOR(j,0,m-1)to[0][0][j]+=e[i][j]*k-e[j][i];
}
V cmin(int&x,int y){if(y-x>>31)x=y;}
V ins(int*a,int x,int*b){FOR(i,0,m-1)b[i]=a[i]+e[x][i]*(1-k)+e[i][x]*(k+1);}
V work(){
    int p=0,q;
    FOR(x,1,m){
        tot=-1,q=p^1;
        FOR(i,0,cnt)FOR(j,0,m-1)if(!(w[p][i]>>j))
            w[q][++tot]=1<<j|w[p][i],ins(to[p][i],j,to[q][tot]);
        FOR(i,0,cnt)FOR(j,0,m-1)if(~w[p][i]>>j&1)
            cmin(f[1<<j|w[p][i]],f[w[p][i]]+to[p][i][j]*x);
        p=q,cnt=tot;
    }
    cout<<f[S];
}
int main(){
//  freopen("test.in","r",stdin);
    input();
    init();
    work();
    return 0;
}

这份代码在 LOJ 上可以通过，但是在洛谷上无法通过...

如果有人知道什么高妙的卡常方法，请务必告诉我。