$$\color{Purple}{kuangbin题解目录}$$
描述
给定一个 $n$ 个点 $m$ 条边的无重边无自环的无向图。
点的编号 $1 \\sim n$。
请你从任意一点出发,遍历图中的所有点,要求:
- 在遍历过程中,每个点最多遍历两次。
- 遍历总路程尽可能短。
输出最短总路程的长度。
输入格式
输入包含多组测试数据。
每组数据第一行包含两个整数 $n,m$。
接下来 $m$ 行,每行包含三个整数 $a,b,c$,表示点 $a$ 和点 $b$ 之间存在一条边,长度为 $c$。
输出格式
每组数据输出一行答案,表示最短总路程的长度,如果无解,则输出 $\-1$。
数据范围
最多包含 $100$ 组数据。
$2 \\le n \\le 10$,
$1 \\le m \\le \\frac{n(n-1)}{2}$。
$1 \\le a,b \\le n$,
$1 \\le c \\le 100$
输入样例:
2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10
输出样例:
100
90
7
思路
- 可采用
dfs
的思想解决,但是效率很低,标记数组用作计数数组;- 可采用
三进制压缩
的思想来解决,该题要求每个点至少访问一次,至多访问两次,使用二进制无法压缩该状态,二进制只能表示访问过($1$)或没有访问过($0$).可使用三个数($0,1,2$)来压缩状态,分别表示没有访问过,访问过一次,访问过两次.- 设$dp(i,j)$表示当前状态$j$时,且最后到达点$i$的最小权值和.其中状态$j$表示的是三进制下,每个数位代表经过每个点的次数.
- 假设点$k$可转移到点$i$,当前状态是$state’$,则最后到达点$k$,可表示为$dp(k,state’)$,则$dp(i,state’+pow3(i))$转移方程: $dp(i,state’+pow3(i))=min(dp(i,state’+pow3(i)),dp(k,state’)+val[k][i])$,其中$pow3(i)$表示$3$的$i$次方
- 第一种采用
链式前向星
存图,第二种采用邻接矩阵
存图(记得初始化).
代码
- 此代码为
dfs
版本,需加$O(2)$优化(卡时间,会$tle9/10$),其次也会卡$min$函数(会$tle8/10$).其中在hdu会内存超限
// Problem: 旅行
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4237/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-13 11:58:38
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#pragma GCC optimize(2)
//由于这题卡时间,可用O(2)解决
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 15
#define MAXM 100
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,m;
int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;//无向图(n*(n-1)/2*2=n*(n-1))
int vis[MAXN];
int res;
void add(int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
void dfs(int root,int cnt,int sum)//root当前点,cnt记录访问元素个数,sum记录当前顺序的结果
{
if(sum>=res)//剪枝(当前的和比结果还大,舍掉)
return ;
if(cnt==n)
{
res=sum;//由于前面的剪枝,当前的sum一定是最优解
//res=min(res,sum);
//此处会卡min函数
return ;
}
for(int i=head[root];i!=-1;i=nex[i])
{
int j=ed[i];
if(vis[j]==2)//每个点最多访问两次
continue;
vis[j]++;
dfs(j,cnt+(vis[j]==1),sum+val[i]);
//遍历下一个点
vis[j]--;
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
while(cin >> n >> m)
{
memset(head,-1,sizeof(head));
idx=0;
res=inf;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);//正向边
add(b,a,c);//反向边
}
for(int i=1;i<=n;i++)
{
vis[i]++;
dfs(i,1,0);
vis[i]--;
}
if(res!=inf)
cout << res << endl;
else cout << -1 << endl;
}
return 0;
}
三进制压缩
解法
// Problem: 旅行
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4237/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-13 11:58:38
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 15
#define MAXM 60000
//pow3[10]=59049;
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,m;
int pow3[MAXN];//存3的次方
int cnt[MAXN][MAXM];//存状态j下的第i位的个数
int f[MAXN][MAXM];//dp所用
int val[MAXN][MAXN];//存i-->j的长度
void init()
{
pow3[0]=1;
for(int i=1;i<=10;i++)
pow3[i]=pow3[i-1]*3;
//cout << pow3[10] << endl;
for(int j=0;j<pow3[10];j++)
{
int num=j;
for(int i=0;i<=9;i++)
{
cnt[i][j]=num%3;
num/=3;
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
init();
while(cin >> n >> m)
{
memset(val,0x3f,sizeof(val));
memset(f,0x3f,sizeof(f));
for(int i=1;i<=m;i++)
{
int a,b,c;
cin >> a >> b >> c;
a--,b--;//点的下标从0开始
val[a][b]=val[b][a]=min(val[a][b],c);
}
int res=inf;
for(int i=0;i<=n-1;i++)
f[i][pow3[i]]=0;
for(int state=0;state<pow3[n];state++)//枚举状态state
{
int flag=1;
for(int k=0;k<=n-1;k++)
{
if(cnt[k][state]==0)//表示该点未访问
flag=0;
if(f[k][state]==inf)//当前状态未到达
continue;
for(int i=0;i<=n-1;i++)
{
//当前点重合或者当前状态下i已经访问过2次
if(i==k||cnt[i][state]==2)
continue;
//k无法直接到达i
if(val[k][i]==inf)
continue;
f[i][state+pow3[i]]=min(f[i][state+pow3[i]],f[k][state]+val[k][i]);
}
}
if(flag==1)
for(int i=0;i<=n-1;i++)
res=min(res,f[i][state]);
}
if(res==inf)
cout << -1 << endl;
else cout << res << endl;
}
return 0;
}
状态压缩可以的