题解 P4802 【[CCO 2015]路短最】

YellowBean_Elsa · 2019-08-21 18:43:50 · 题解

这是一道很好的练状态压缩的题

一看数据范围就知道时间复杂度是 2^n 级别的。

由于和路径长度有关，想到了经典的状压：

dp[ i ][ j ] 表示状态为 i，现在在节点 j 的最长路径

具体解释（不熟悉状压的人）：

    设 i = 39 = 32 + 4 + 2 + 1 = 100111 (二进制), 则

    状态 i 表示已经过0，1，2，5号节点，因为100111从

    右往左数第0，1，2，5位为1。

转移方程：dp[ i ][ v ] = dp[ j ][ u ] + e[ u ][ v ]

其中 e 是邻接矩阵，u，v 是用来转移的边的起点和终点，

状态 j 应该比状态 i 少一个位置 v 上的 1，因为 j 时 v 还没走过。

由于不会从已经过的节点转移过来，所以不会重复经过节点。

上代码（有些邪恶的常数优化）

//码风丑请见谅 
//Luogu P4802 O（2^n * n^2）
#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
int n,m;
int dp[1<<18][18];
int e[18][18],x,y;
inline int Max(int x,int y){
    if(x>y)return x;
    return y;
}
int ans;
int main(){
    n=read(),m=read();
    //读入，邻接矩阵存图 
    for(re int i=1;i<=m;i++){
        x=read(),y=read();
        e[x][y]=read();
    }
    memset(dp,0x8f,sizeof(dp));//-INF 
    dp[1][0]=0;//初始化：只经过起点位移（划掉）路程为0 
    //开始dp 
    for(re int i=3;i<(1<<n);i+=2)//O(2^n)枚举初始状态
    //常数优化1：只枚举经过了0号节点的状态（奇数） 
        for(re int u=0;u<n;u++)//O(n)枚举起点 
            if((i>>u)&1)//判断u节点是否走过（状压中的经典骚操作 %%%）  
                for(re int v=1;v<n;v++)//O(n)枚举终点
                //常数优化2：枚举终点时不枚举0（差不多一点用都没有） 
                    if(((i>>v)&1)&&e[u][v])
                        dp[i][v]=Max(dp[i][v],dp[i-(1<<v)][u]+e[u][v]);//转移方程 
    //不用写大括号真幸福 #Q#_A_#Q#           
    for(re int i=(1<<(n-1))+1;i<=(1<<n)-1;i+=2)
    //常数优化3：只从经过了0号和n-1号节点的状态中挑选答案 
        ans=Max(ans,dp[i][n-1]);
    printf("%d\n",ans);
    return 0;
}

会树状数组的看过来！

正经的非常数的优化！

利用传奇的lowbit操作可以将复杂度优化到O(2^n \times(log n)^2)

每次枚举起点和终点时，我们不再盲目地一位位试，而是直接用