一道耗费了本蒟蒻与某机房卷王半天的恶心题
题目描述
给定一个图，求每个 X 连通块之间的最短 Hamilton 路径。假如您不知道 Hamilton 路径是什么
分析
这题本质上是 Hamilton 路径的模板题，但是难就难在题目并没有直接将一个抽象过的无向图给你，而是给了一个具体的地图。那么我们第一步就应该将这个地图抽象成一个无向图。
First
首先我们来找连通块。记 \(Belong_{x,y}\) 为坐标为 \((x,y)\) 的 'X' 所属的连通块， \(tot\) 为连通块的总数， \(mp_{x,y}\) 为我们存的地图（将 'S' 存为 \(1\)，'X' 存为 \(0\)，'.' 存为 -\(1\) ）。则我们可以用 DFS 来求连通块 （我是不会说我不会 BFS 的）
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
ll belong[ma][ma],tot=0;
ll mp[ma][ma];
void dfs1(ll x,ll y){
if(x>n||y>m||x<1||y<1) return;//到边界停止
if(mp[x][y]!=0||belong[x][y]) return;//找过了或不是陆地就不找了
if(mp[x][y]==0){
belong[x][y]=tot;//记录连通块
}
for(ll i=0;i<4;i++){
ll xx=x+dx[i],yy=y+dy[i];//位移深搜
dfs1(xx,yy);
}
}
Second
找完了联通块，就开始建图了。我们记 \(w_{i,j}\) 为联通块 \(i\) 到 \(j\) 的最短路径。那么我们要如何求这个最短路径呢？类比双端队列优化的 SPFA，我们用一个双端队列对每一个连通块都跑一遍 BFS，记 \(dis_{i,j}\) 为当前连通块到 \((i,j)\) 的最短路径，再去用 \(dis_{i,j}\) 的最小值更新 \(w_{i,j}\) 即可。
deque<pair<ll,ll>> q;
ll dis[ma][ma];
ll w[16][16];
void bfs(){
while(q.size()){
ll x=q.front().first,y=q.front().second;
q.pop_front();
for(ll i=0;i<4;i++){
ll xx=x+dx[i],yy=y+dy[i];
if(xx>n||yy>m||xx<1||yy<1) continue;//越界
if(dis[xx][yy]||mp[xx][yy]==-1) continue;//访问过
//如果是 'X' ，则推到队首，距离不变
if(mp[xx][yy]==0){
dis[xx][yy]=dis[x][y];
q.push_front(make_pair(xx,yy));
}
//如果是 'S' ，则推到队尾，距离加1
else if(mp[xx][yy]==1){
dis[xx][yy]=dis[x][y]+1;
q.push_back(make_pair(xx,yy));
}
}
}
}
//in main()
memset(w,0x3f,sizeof(w));
for(ll i=1;i<=tot;i++){
memset(dis,0,sizeof(dis));
for(ll j=1;j<=n;j++){
for(ll k=1;k<=m;k++){
if(belong[j][k]==i){
//如果(j,k)属于第i个连通块，则推到队首
q.push_front(make_pair(j,k));
dis[j][k]=1;//小技巧:为了防止0在 BFS 时一直不被更新，初始便设置为1。
}
}
}
bfs();
for(ll j=1;j<=n;j++){
for(ll k=1;k<=m;k++){
//(j,k)为枚举的点
for(ll cx=1;cx<=n;cx++){
for(ll cy=1;cy<=m;cy++){
//(cx,cy)为属于第i个连通块的点
if(belong[j][k]&&belong[cx][cy]&&belong[cx][cy]==i){
w[i][belong[j][k]]=min(w[i][belong[j][k]],dis[j][k]-dis[cx][cy]);//更新w
}
}
}
}
}
}
Final
现在，我们总算将这题最最 恶心 难的地方处理完啦，接下来便是纯纯的 最短 Hamilton 路径 板子。但是注意我们是可以随便选起点的，所以要对每一个点作为起点都跑一遍状压 DP，求出最小的答案即可。
状压 DP 具体见这题
ll dp[16][1<<16];
memset(dp,0x3f,sizeof(dp));
for(ll i=1;i<=tot;i++) dp[i][1<<(i-1)]=0;
for(ll i=1;i<=tot;i++){
for(ll j=1<<(i-1)+1;j<1<<tot;j++){
for(ll k=1;k<=tot;k++){
if((j>>(k-1))&1){
for(ll l=1;l<=tot;l++){
if((j^1<<(k-1))>>(l-1)&1){
dp[k][j]=min(dp[k][j],dp[l][j^1<<(k-1)]+w[l][k]);
}
}
}
}
}
}
ll ans=inf;
for(ll i=1;i<=tot;i++) ans=min(ans,dp[i][(1<<tot)-1]);
完整代码
#include<bits/stdc++.h>
#define ll long long
#define ma 100
#define mod 1000000007
#define il inline
using namespace std;
const ll inf=1e18+10;
ll read(){
char ch=getchar();
ll x=0,f=1;
while(ch>'9'||ch<'0'){
if(ch=='-') f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
ll n,m;
ll mp[ma][ma];
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
ll dp[16][1<<16];
ll w[16][16];
ll belong[ma][ma],tot=0;
deque<pair<ll,ll>> q;
ll dis[ma][ma];
void dfs1(ll x,ll y){
if(x>n||y>m||x<1||y<1) return;
if(mp[x][y]!=0||belong[x][y]) return;
if(mp[x][y]==0){
belong[x][y]=tot;
}
for(ll i=0;i<4;i++){
ll xx=x+dx[i],yy=y+dy[i];
dfs1(xx,yy);
}
}
void bfs(){
while(q.size()){
ll x=q.front().first,y=q.front().second;
q.pop_front();
for(ll i=0;i<4;i++){
ll xx=x+dx[i],yy=y+dy[i];
if(xx>n||yy>m||xx<1||yy<1) continue;
if(dis[xx][yy]||mp[xx][yy]==-1) continue;
if(mp[xx][yy]==0){
dis[xx][yy]=dis[x][y];
q.push_front(make_pair(xx,yy));
}
else if(mp[xx][yy]==1){
dis[xx][yy]=dis[x][y]+1;
q.push_back(make_pair(xx,yy));
}
}
}
}
int main(){
n=read(),m=read();
for(ll i=1;i<=n;i++){
char x[100];
cin>>x+1;
for(ll j=1;j<=m;j++){
if(x[j]=='.') mp[i][j]=-1;
if(x[j]=='X') mp[i][j]=0;
if(x[j]=='S') mp[i][j]=1;
}
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
if(!belong[i][j]&&!mp[i][j]){
++tot;
dfs1(i,j);
}
}
}
memset(w,0x3f,sizeof(w));
for(ll i=1;i<=tot;i++){
memset(dis,0,sizeof(dis));
for(ll j=1;j<=n;j++){
for(ll k=1;k<=m;k++){
if(belong[j][k]==i){
q.push_front(make_pair(j,k));
dis[j][k]=1;
}
}
}
bfs();
for(ll j=1;j<=n;j++){
for(ll k=1;k<=m;k++){
for(ll cx=1;cx<=n;cx++){
for(ll cy=1;cy<=m;cy++){
if(belong[j][k]&&belong[cx][cy]&&belong[cx][cy]==i){
w[i][belong[j][k]]=min(w[i][belong[j][k]],dis[j][k]-dis[cx][cy]);
}
}
}
}
}
}
memset(dp,0x3f,sizeof(dp));
for(ll i=1;i<=tot;i++) dp[i][1<<(i-1)]=0;
for(ll i=1;i<=tot;i++){
for(ll j=1<<(i-1)+1;j<1<<tot;j++){
for(ll k=1;k<=tot;k++){
if((j>>(k-1))&1){
for(ll l=1;l<=tot;l++){
if((j^1<<(k-1))>>(l-1)&1){
dp[k][j]=min(dp[k][j],dp[l][j^1<<(k-1)]+w[l][k]);
}
}
}
}
}
}
ll ans=inf;
for(ll i=1;i<=tot;i++) ans=min(ans,dp[i][(1<<tot)-1]);
printf("%lld\n",ans);
return 0;
}
部分思想参考了卷王cry
标签：P3070,连通,ma,题解,ll,路径,Travels,dp,dis From： https://www.cnblogs.com/mukar/p/17071899.html