题目描述

你可以通过许多的算法找到从一个地方到另外一个地方的最短路径。人们在他们的车上安装 GPS 设备然后他们的手机告诉他们最快的到达目的地的方式。然而，当在假期时，Troy 喜欢慢慢旅游。他想找最长的到目的地的路径以便他可以在路途中看许多新的以及有趣的地方。 因此，一个有效的路径包含一个不同城市的序列 $c_1,c_2,…,c_k$,并且对于每个$1\le i \le k$ ，有道路从$c_i$通往$c_{i+1}$
他不想重复访问任何城市，请帮他找出最长路径。

输入输出格式

输入格式

第一行输入包括两个整数 $n,m$，分别表示城市总数和连接城市间的道路数，两城市间至多有一条道路。

城市编号从 $0$ 到 $n-1$，Troy 一开始在城市 $0$，城市 $n-1$ 是他的目的地。

接下来 $m$ 行每行三个整数 $s,d,l$，每个三元组表示这里有一条长为 $l$ 的从城市 $s$ 到城市 $d$ 的路。

每条路都是有向的，只能从 $s$ 到 $d$，不能反向。保证有一条从城市 $0$ 到 $n-1$ 的路径。

输出格式

输出一个整数表示以城市 $0$ 为起点，以 $n-1$ 为终点的最长路径长度，并且其中不重复访问城市，路径长度是所经过的道路长度之和。

输入输出样例

输入样例

3 3
0 2 5
0 1 4
1 2 3

输出样例 #1

7

友情提示

最短路为直接走城市 $0$ 至城市 $2$ 的道路，长度为 $5$ km。最长路为 $0$ 至 $1$ 至 $2$， 长度 $4+3=7$ km。

数据范围

对于至少 $30\%$ 的数据，$n\le 8$；
对于 $100\%$ 的数据，有 $2\le n \le 18,$ $1\le m \le n^2-n,$ $0\le s,d \le n-1,$ $s\neq d,$ $1\le l\le 10000$。

解题报告

题意理解

题目要从$0$走到$n-1$,途中节点不重复经过,要求路径最长

算法解析

乍一看可以使用最短路类型的算法,但是题目边权均为正数,

所以我们得换用其他算法解析.

我们着重发现,这道题目的节点数量特别少,因此不妨考虑到状态转移动态规划,这一类算法.

既然算法已经确定了,那么接下来最主要的问题是,如何利用这个算法处理本题.

我们可以利用闫式DP法,来处理本题.

状态表示

题目中当前访问了哪些点,必然是我们需要考虑的问题.

但是最为主要的,还是当前我们所在的点,因为我们要通过这个点,走到其他点.

然后我们状态的表示,肯定是要记录路径长度.

综上所述,我们不难设计如下状态表示.

$f[S][i]$表示为当前已经访问点集合为$s$,而且当前点为$i$

状态转移

我们着重分析一下状态转移,其实因为状态设计很清晰,所以本题转移也不难.

假如说,当前有节点$j$,和节点$k$,而且当前点集合为$s$,那么不难推出一些关系.

首先节点$j$肯定要属于$s$集合内.

也就是,我所在的位置,必须我访问过.

不然的话,这个点我都没有来过,那么我怎么可能当前站在这个点.

然后,节点$k$肯定要不属于集合$s$.

因为题目说了,一个节点不能访问两次和两次以上,而且我当前是从$j$走到$k$.

如果说$k$访问过了,那么我们不就违反了条件了吗?

最后一点,$j$和$k$之间要有边联系.

如果连边都没有,那么怎么走过去呢?

总而言之,我们总结出了三个条件.

1. 节点$j$肯定要属于$s$集合内.
2. 节点$k$肯定要不属于集合$s$.
3. $j$和$k$之间要有边联系.

这就是我们这道题目的状态转移的限制条件.

那么转移方程,自然也就是.

$f[s | (1<<k)]=max(f[s | (1<<k)],f[s][j]+g[j][k])$

代码展示

#include <bits/stdc++.h>
using namespace std;
const int N=19;
int n,m,f[1<<N][N],ans;
vector<int> G[N],V[N];
int dfs(int x,int S)
{
    if(x==n-1)//抵达目的地,不能再走了
        return 0;
    if(f[S][x])//已经访问过了
        return f[S][x];
    int cnt=-1<<20;//当前路径最大值
    for(int i=0; i<G[x].size(); i++)
        if(! (S & (1<<G[x][i]) ) )//g[x][i]表示这个点为当前点
            cnt=max(cnt,V[x][i]+dfs(G[x][i],S | (1<<G[x][i]) ) );
    return f[S][x]=cnt;
}
inline void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back(v);//u连接着v
        V[u].push_back(w);//u,v的边权
    }
    printf("%d\n",dfs(0,1));
}
signed main()
{
    init();
    return 0;
}