首页 > 7.21 华为机试
头像
obey201911212042708
发布于 2021-07-22 05:17
+ 关注

7.21 华为机试

总共就完整写出来了这一道题

题目大意

  • n个点(n<=200)的图,找到当前图最长路径

输入输出

  • 输入:[[1,2,5],[1,3,5],[2,3,10]] // 非原数据

  • 输出:40

思路

  • 写的太紧张了,加上输入输出的处理,想到的就是直接对每个点做bfs,写了个O(N^4)的算法...不过因为数据量这也能过

  • 时间复杂度:遍历所有点NO(N),每个点进行bfsO(N),其中bfs遍历所有可能的边对,最多n-1+n-2+...+1,O(N^2),每个点集对又需要O(N),O(N^4)的时间复杂度了

  • 用邻接矩阵来存会好得多,但我想的数据量不大赶紧A了..

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 205;
int g[N][N];

vector<int> ps; // point set, 点集, 记录所有当前使用的点, 

int bfs(int st)
{
    queue<PII> q;
    q.push({st, 0});
    int res = 0;

    while(!q.empty())
    {
        auto tmp = q.front();
        q.pop();

        int p = tmp.first, d = tmp.second;
        for(int i = 0; i < ps.size(); i++)
        {
            int end_p = ps[i];

            if(g[p][end_p] != -1)
            {
                q.push({end_p, d + g[p][end_p]});
                res = max(res, d + g[p][end_p]);
            }
        }
    }
    return res;
}

int main()
{
    string s;
    cin>>s;     // 输入时低位在右,高位在左

    // 对数值进行初始化
    int cnt = 0;
    int st, e, dis;                 // st 起始点,e 终点,dis 距离
    int tmp = 0;                    // 暂存数值元素
    bool vis[N];                    // 用于确定哪些点没有被使用
    memset(vis, false, sizeof vis); 
    memset(g, -1, sizeof g);        // 初始化所有的距离

    for(int i = 0; i < s.size(); i++)
    {
        // cnt用于确定是开始点还是end点, isdigit 判断当前位置字符是否为数字
        if(isdigit(s[i]) && cnt == 0)
        {
            tmp = 0;
            while(isdigit(s[i]))     //需要处理多个字符的情况,从左到右读入我们的数
            {
                tmp *= 10;
                tmp += (s[i] - '0');
                i++;
            }
            st = tmp;
            cnt++;
        }
        else if(isdigit(s[i]) && cnt == 1)
        {
            tmp = 0;
            while(isdigit(s[i]))     //需要处理多个字符的情况
            {
                tmp *= 10;
                tmp += (s[i] - '0');
                i++;
            }
            e = tmp;
            cnt++;
        }
        else if(isdigit(s[i]) && cnt == 2)
        {
            cnt = 0;
            tmp = 0;
            while(isdigit(s[i]))     //需要处理多个字符的情况
            {
                tmp *= 10;          
                tmp += (s[i] - '0');
                i++;
            }
            dis = tmp;

            if(!vis[st])
            {
                ps.push_back(st);
                vis[st] = true;
            }

            if(!vis[e])
            {
                ps.push_back(e);
                vis[e] = true;
            }
            g[st][e] = dis;

        }
    }


    int res = 0;
    for(int i = 0; i < ps.size(); i++) // 对所有的点都进行bfs,找到最大的路径
    {
        res = max(res, bfs(ps[i]));
    }
    cout<<res<<endl;

}

全部评论

(7) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐