自动搬运

查看原文

来自洛谷，原作者为

	YellowBean_Elsa You find me waiting in the wings......

搬运于2025-08-24 22:03:46，当前版本为作者最后更新于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)$

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

$lowbit$ 找到 $1$ 个符合要求的点

详见代码：

#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[20][20],x,y;
inline int lowbit(int x){//That's it！ 
	return x&(-x);
}
inline int Max(int x,int y){
	if(x>y)return x;
	return y;
}
int Log[1<<19];//记录每个lowbit值映射到哪个节点 
inline void init_log(){
	for(re int i=0;i<n;i++)
		Log[1<<i]=i;
}
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));
	dp[1][0]=0; 
	init_log();//初始化Log数组 
	int u,v;
	for(re int i=3;i<(1<<n);i+=2){
		int j1;
		for(re int k1=i;k1;k1-=j1){
		//*每次找到这个二进制数最靠右的一个1，转移完后减掉* 
			j1=lowbit(k1);
			u=Log[j1];//j1对应的点即为起点 
			int j2;
			for(re int k2=i;k2;k2-=j2){//同上 
				j2=lowbit(k2);
				v=Log[j2];
				if(e[u][v])
					dp[i][v]=Max(dp[i][v],dp[i-j2][u]+e[u][v]); 
			}
		}
	}
	for(re int i=(1<<(n-1))+1;i<(1<<n);i+=2)
		ans=Max(ans,dp[i][n-1]);
	printf("%d\n",ans);
	return 0;
}

最后祝愿CCF能在与教育部的斗争中获胜，赢回我们的NOIP