欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

球队“食物链”

程序员文章站 2022-06-07 09:52:53
...

竹杖芒鞋轻胜马

谁怕?

一蓑烟雨任平生

球队“食物链”

这是PTA上一道作业题,大概就是在有向图中找出一个字典序最小的环,要求这个环连接了所有的点。

首先想到的就是DFS了,思路如下:

  1. 根据输入,建立所有的有向边,当然可能出现双向的
  2. 使用深度优先遍历,用一个vector记录路径,用一个vis数组记录当前路径经过的点
  3. 每进入下一个点前,判断这个点有没有访问过,是不是连通
  4. 如果记录路径的vector存下了n个点,说明已经存下了所有点了,然后看首尾相等吗
  5. 首尾相等则说明找到答案了,我们是按照从小到大找的,所以不用考虑字典序

看上去没大问题了,写下来,一交,超时了。

想了好多可能超时的点,都觉得不科学,按理说已经不能降低复杂度了。

只能搜一下了,看了下博客上别人的题解,才意识到问题没那么简单。

这个题目有几个信息必须抓住:

  1. 环上包括了所有的点
  2. 字典序最小,则意味着环要有个头的话,一定是1!
  3. 第三点最重要:如果剩下的点中没有能和1相连通的,就不用遍历了,因为没有能够连接头的了,成不了环

有了以上分析,就可以下写出下面的代码了:

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int g[21][21];
int n;
vector<int> ans;
bool vis[21];

void dfs(int root, vector<int> &tpath, bool &flag) {
    if (flag) return ;
    if (tpath.size() == n && g[root][1] == 1) {
        ans = tpath;
        flag = true;
    }
    bool cango = false;
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && g[i][1] == 1)
            cango = true;
    }
    if (!cango) return ;
    for (int next = 1; next <= n; next++) {
        if (!vis[next]) {
            if (g[root][next] == 1) {
                vis[next] = true;
                tpath.push_back(next);
                dfs(next, tpath, flag);
                tpath.pop_back();
                vis[next] = false;
            }
        }
    }
}

int main() {
    cin >> n;
    getchar();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            char ret;
            scanf("%c", &ret);
            if (ret == '-') g[i][j] = 0;
            else if (ret == 'W') g[i][j] = 1;
            else if (ret == 'L') g[j][i] = 1;
        }
        getchar();
    }
    vector<int> tpath;
    bool flag = false;
    for (int i = 1; i <= n; i++) {
        vis[i] = true;
        tpath.push_back(i);
        dfs(i, tpath, flag);
        tpath.pop_back();
        vis[i] = false;
    }
    if (flag) {
        for (int i = 0; i < n; i++) {
            if (i != n - 1)
                printf("%d ", ans[i]);
            else
                printf("%d", ans[i]);
        }
    } else printf("No Solution");
    return 0;
}
相关标签: PTA