引用

这题并不是一定要dfs,也可以直接用邻接矩阵判断,但是因为想熟悉一下dfs,所以采用了邻接表这个方法,邻接矩阵的可以参考一下这位大佬的代码

东篱下の悠然 2020年11月28日天梯赛GPLT总决赛(全部题目 + 189分代码答案)

题目描述

一个旅游景点,如果被带火了的话,就被称为“网红点”。大家来网红点游玩,俗称“打卡”。在各个网红点打卡的快(省)乐(钱)方法称为“攻略”。你的任务就是从一大堆攻略中,找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。

样例

输入格式

首先第一行给出两个正整数:网红点的个数 $N(1<N≤200)$ 和网红点之间通路的条数 $ M $ 。随后 $ M $ 行,每行给出有通路的两个网红点、以及这条路上的旅行花费(为正整数),格式为“网红点1 网红点2 费用”,其中网红点从 $ 1 $ 到 $ N $ 编号;同时也给出你家到某些网红点的花费,格式相同,其中你家的编号固定为 0

再下一行给出一个正整数 K,是待检验的攻略的数量。随后 K 行,每行给出一条待检攻略,格式为: $n V_1V_2 ⋯ V_n$
​​
其中 $ n(≤200) $ 是攻略中的网红点数,$V_i$ 是路径上的网红点编号。这里假设你从家里出发,从 $V_​1$ 开始打卡,最后从 $V_​n$回家。

输出格式

在第一行输出满足要求的攻略的个数。

在第二行中,首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号(从 1 开始),然后输出这个攻略的总路费,其间以一个空格分隔。如果这样的攻略不唯一,则输出序号最小的那个。

题目保证至少存在一个有效攻略,并且总路费不超过 $10^9$ 。

输入样例

6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6

输出样例

3
5 11

样例说明:

第 2、3、4、6 条都不满足攻略的基本要求,即不能做到从家里出发,在每个网红点打卡仅一次,且能回到家里。所以满足条件的攻略有 3 条。

第 1 条攻略的总路费是:(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14;

第 5 条攻略的总路费同理可算得:1 + 1 + 1 + 2 + 3 + 1 + 2 = 11,是一条更省钱的攻略;

第 7 条攻略的总路费同理可算得:2 + 1 + 1 + 2 + 2 + 2 + 1 = 11,与第 5 条花费相同,但序号较大,所以不输出。


算法

(记忆化搜索) $O(n^2)$

这个样例解释有点小坑,反正我是没看出来。它指的每个点不是攻略给出的点,而是1~n个点2333。由题目的意思我们可以知道,只需要dfs搜一下每一个攻略,看看是不是能到终点,并且遍历了n个点,然后记录一下费用和攻略个数即可。

时间复杂度 $O(n)$

鸽了

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210 , M = 100010;

int n , m , k , sum , f;
int INF = 0x3f3f3f3f;

int h[N] , e[N * N] , ne[N * N] , idx;
int path[M] , g[N][N];
long long res[M];
bool st[N];

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}

int dfs(int u , int idx)
{
    //虽然总费用不超过10的9次方,但是int也才2开头的九位数,所以用LL
    long long sum = 0;
    
    //表示这个点已经被遍历过了
    st[u] = true;
    
    if(u == 0)
    {
        //标记这个攻略能回到起点
        f = 1;
        return sum;
    }
    
    //如果当前的点为-1表示不能往下走所以直接返回0;
    if(h[u] ==  -1) return 0;
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {   
            //如果这个点没有被遍历过,并且是路线的下一个点,那么就继续走
            if(path[idx] == j) sum += g[u][j] + dfs(j , idx + 1);
        }
    }
    // 返回以u为起点的费用
    return sum;
}

int main()
{
    
    long long minx = INF;
    
    cin >> n >> m;
    
    //初始化头结点和攻略路径
    memset(h , -1 ,sizeof h);
    memset(path , -1 , sizeof path);
    
    for(int i = 0; i < m; i ++)
    {
        int a , b , c;
        cin >> a >> b >> c;
        //因为这题是无向有环图,所以要加两条边,然后用g记录费用,也就是邻接矩阵
        add(a , b);
        add(b , a);
        g[a][b] = g[b][a] = c;
    }
    
    cin >> k;
    
    int cnt = 0;
    for(int i = 0; i < k; i ++)
    {
        int t , flag = 0;
        cin >> t;
        
        for(int j = 0; j < t; j ++) cin >> path[j];
        //将起点加入路径,作为终点
        path[t] = 0;
        //如果这个点的起点不是零能到的点,那么后续就不需要继续了
        for(int j = h[0]; j != -1; j = ne[j])
            if(e[j] == path[0]) 
                flag = 1;
            
        if(flag) 
        {
            int t1 = 0;
            //dfs时从攻略的起点开始会好一点
            res[i] += dfs(path[0] , 1) + g[0][path[0]];
            //看一下是否n个点都有且只到过一次
            for(int i = 0; i <= n; i ++) if(st[i]) t1++;
            //如果到了起点并且是n个点都遍历了,那么就更新minx,并且cnt++,n+1是因为包括了0这个点,不这么写也可以
            if(f && t1 == n + 1) minx = min(res[i] , minx) , cnt ++;
            f = 0;
        }
        
        memset(path , -1 , sizeof path);
        memset(st , 0 , sizeof st);
    }
    
    cout << cnt << endl;
    //遍历数组看看最先等于minx是哪一个
    for(int i = 0; i < k; i ++)
    {
        if(res[i] == minx)
        {
            cout << i + 1 << ' ' << res[i] << endl;
            break;
        }
    }
    
    return 0;
}

Q.E.D.


都懂一点,不是很懂的小捞仔