一道较有思考意义的题目,其最主要的问题便是题目中的一句话:这条道路的长度 × 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量(包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋),如果使花费最小化,那么挖通的连通图一定为一棵树,根为赞助商帮你打的那个点,那么此时从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量便可以看做点的深度,那么我们可以考虑一下挖通后的图中,有哪些点深度都为$1$,哪些都为$2$....,则我们可以考虑一层一层的加点,按深度作为转移,以点状态作状态即可。
当然,我还有一种想法,有看法的在评论区发表发表qwq。
考虑一个点一个点的加,这样的话我们便可以维护一种点状态下的每个点的深度,由于考虑到可能存在不同状态转移同状态的情况,导致点状态深度错误,所以我考虑加上一维来表示当前状态是由哪个点进行添加而转移来避免问题,由于深度存储需要一定的根,所以我们还需要枚举赞助商开槽点,理想时间复杂度为$n^3 *2^n$。
不考虑点状态深度错误的代码如下 :
#include<bits/stdc++.h>
using namespace std ;
const int Max = 1e3 + 10 , Nax = 13 , Uax = ( 1 << 12 ) + 1 ;
vector < int > Q[Max] ;
int Ans = 1e7 + 10 ;
int Run[Uax][Nax] ;
int W[Nax][Nax] ;
int X , Y , Z ;
int F[Uax] ;
int N , M ;
int main( ) {
scanf("%d%d" , &N , &M ) ;
for(int i = 1 ; i <= N ; i ++ ) for(int l = 1 ; l <= N ; l ++ ) W[i][l] = 1e7 + 10 ;
while( M -- ) {
scanf("%d%d%d" , &X , &Y , &Z ) ;
if( W[X][Y] == 1e7 + 10 ) Q[X].push_back( Y ) , Q[Y].push_back( X ) ;
W[X][Y] = min( W[X][Y] , Z ) , W[Y][X] = min( W[Y][X] , Z ) ;
}
for(int Min = 1 ; Min <= N ; Min ++ ) {
for(int i = false ; i <= Uax - 1 ; i ++ ) for(int H = false ; H <= Nax - 1 ; H ++ ) F[i] = 1e7 + 10 ;
F[1 << ( Min - 1 )] = false ;
for(int i = 1 ; i <= ( 1 << N ) - 1 ; i ++ ) for(int l = 1 ; l <= N ; l ++ ) {
if( !( ( i >> ( l - 1 ) ) & 1 ) || !( ( i >> ( Min - 1 ) ) & 1 ) ) continue ;
int Zan = i , P = l , Nul = 1 ;
while( P != Min ) { // 从点l往上走走到根节点,走了几步就代表深度为几
int You = Run[Zan][P] ;
Zan -= ( 1 << ( P - 1 ) ) ;
P = You ;
Nul ++ ;
if( Nul >= N || !P ) break ;
}
if( Nul >= N || !P ) continue ;
for(int Tr = false ; Tr < Q[l].size( ) ; Tr ++ ) { int K = Q[l][Tr] ;
if( ( i >> ( K - 1 ) ) & 1 ) continue ;
if( F[i] + Nul * W[l][K] <= F[i + ( 1 << ( K - 1 ) ) ] ) { //如果更优则替换
F[i + ( 1 << ( K - 1 ) )] = F[i] + Nul * W[l][K] ; // 转移
Run[i + ( 1 << ( K - 1 ) )][K] = l ; // 更新点状态i + ( 1 << ( K - 1 ) )中,点K的上一步的点
//错因也在这,i + ( 1 << ( K - 1 ) )可能多次被转移,而Run的值无法做到全局更新导致错误
}
}
}
Ans = min( Ans , F[( 1 << N ) - 1] ) ;
}
printf("%d\n" , Ans ) ;
return false ;
}
5 5
1 2 4
1 3 1
1 4 1
2 3 2
2 5 4
正确答案:$12$
实际输出:$11$
你想到后效性了吗?
显然是没有后效性的
就算按照记录最后一步避免转移冲突的办法,深度也始终没法求
嗯,我没想到,我再想想
手动模拟过了吗?(就是模拟你的算法)
模拟过了,现在也是知道有什么问题的,但是本蒟蒻不知道怎么解决,反正周围大部分人都说这个做法无解,但我还是想问问大众
orz
所以你有什么看法吗
你觉得我这种LJ能有啥想法....
问题不大