题目描述
/*
0 1 2 3
在内部走过点的数目对我们来说毫无关系只关心你我们用过的点数
(dfs)是遍历没有用过的点,
而我们在遍历的的过程中,我们并不在意遍历的数字顺序是什么,我们只需要关心这个数字我们是否遍历过,
以及我最后停在了哪一个点上(这个点就是我们的最后的点的坐标)
我们最后关心的还是哪一个点被用过,而且停留在了哪一个点,
这样就可以确定我们的正规的的搜索状态是什么。。。
0 -> 1 -> 2 -> 3 如果 为18(留)
//0 -> 1 -> 3 -> 2 如果 为20 (不留)
0 -> 2 -> 1 -> 3
0 -> 2 -> 3 -> 1
0 -> 3 -> 1 -> 2
0 -> 3 -> 2 -> 1
(总共六种方式 3! = 2*3 = 6)
开始抓关键!!!
1.那些点被用过?
2.目前停在哪个点上?(这两个问题可以看作一个二维的矩阵)
算总共的状态量有多少~
第一问的(一维的)状态一共有2^20次方的
第二问总共停在的点数可能有20个(从题目的数据范围里得出的)
总共的数据范围大概是2^20*20 = 2 * 10^7 (相比暴力的20!数据范围小太多了 两千万还能接受的!!)
然后我们分析完所有的状态一共有20000000个
然后就是状态的计算过程:
声明下变量代表的意思:
state是当前哪些点被用过,
j表示我们最后停在了哪些点上
f[state][j]
接下来就是计算f[state][j]这个点的状态:
此处用的是枚举:枚举一下我们从哪一个点转移过来,
我们遍历一下所有的点,
假设我们从k转移过来的话
f[state][j] = f[state_k][k] +weight[k]j
在state_k这个点的状态 + weight[k][j] 中 j这个点之后 可以得到我们这个state这个状态,
也就是说在state这个集合中(这个集合中包括哪些点,哪些点表示被遍历过的),
state_k(这个集合表示k这个状态里边对应哪些点)
如果这个f[state][j] 表示是从f[state_k][k] - weight[k][j]这个状态转移过来的话,
在声明下啊, (f[state_k][k] - weight[k][j])这个状态就是从k走到(state_k = state)状态之后,
除掉 j之后的集合,
并且state_k要包含k,
应为这个状态要合法(什么是合法呢???),
所以说我们的状态转移的话,就需要枚举(state_k中)这样的k,
k满足的条件(state这个集合去掉j之后的,state_k这个集合中的所有的点)
也就是从state_k中枚举k出来算一下在f[state][k]中k这个状态中表示的最优值再加上从k到j转移的这个最优值(weight[k][j]),
就是f[state][j]这个最优值了
最后一个问题!!
我们这个state怎么来表示这个集合呢,因为我们的第一印象看这个state最多也只是一个一维数组中的变量而已,
在这里,
我们可以用位运算表示,
就是用一个二进制的整数表示一个state,
state表示的是一个 20位 的整数,
但是,20位里边有可能是0,也有可能是1,
上述将state变成一个集合的办法就是
状态压缩!!!(圈重点考试要考!!!)
0 1 4
压缩完是10011
整个的时间复杂度就是状态的数量(2107)乘以状态转移的复杂度(20)大概是4亿,题目是7亿
如果这一位为1的话就表示这个点存在, 0就不存在
state_k = state
*/
===
时间复杂度
4亿
#include<iostream>
#include<cstring>
#include<algorithm
using namespace std;
const int N = 20,M = 1<<20;//M相当于1*(2^20) 也就是十进制的1048576
int n;
int f[M][N],weight[N][N];
int main(){
cin >> n;
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
cin >> weight[i][j];
memset(f,0x3f,sizeof f);//无穷大
f[1][0] = 0;//一开始还没有走过任何的路程所以初始化为零
//first我们枚举下所有的状态
for(int i = 0;i < 1<<n;i++)
for(int j = 0;j < n;j++)
//判断末端整数位个位数字是不是1,右移到个位与上一,判断是0还是1
//如果个位是1就是合法的
if(i >> j & 1)
//枚举下整数
//当前状态是i,看下state_k(后面)这个状态 把第j位减去,还没有走到j
for(int k = 0;k < n;k++)
//判断整数位是否状态为1
if(i - (1<<j) >> k & 1)
//如果是1则符合条件
f[i][j] = min(f[i][j],f[i - (1 << j)][k] + weight[k][j]);
cout << f[(1 << n) - 1][n - 1] << endl;
return 0;
}