头像

JackFrost

南昌大学




离线:5小时前


活动打卡代码 AcWing 1601. 在线地图

JackFrost
13小时前
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 510;

PII g[N][N];
bool st[N];
int dist[N], ti[N];
vector<int> path_d[N], path_t[N];

int n, m, S, T;

void dijkstra_dist()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0; ti[S] = 0; path_d[S].push_back(S);

    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 0; j < n; j ++)
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;

        for(int j = 0; j < n; j ++)
        {
            if(dist[j] > dist[t] + g[t][j].first)
            {
                dist[j] = dist[t] + g[t][j].first;
                ti[j] = ti[t] + g[t][j].second;
                path_d[j].assign(path_d[t].begin(), path_d[t].end()); 
                path_d[j].push_back(j);
            }
            else if(dist[j] == dist[t] + g[t][j].first)
            {
                if(ti[j] > ti[t] + g[t][j].second)
                {
                    ti[j] = ti[t] + g[t][j].second;
                    path_d[j].assign(path_d[t].begin(), path_d[t].end()); 
                    path_d[j].push_back(j);
                }
            }
        }
    }
}

void dijkstra_time()
{
    memset(ti, 0x3f, sizeof ti);
    ti[S] = 0; path_t[S].push_back(S);

    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 0; j < n; j ++)
            if(!st[j] && (t == -1 || ti[j] < ti[t]))
                t = j;

        st[t] = true;

        for(int j = 0; j < n; j ++)
        {
            if(ti[j] > ti[t] + g[t][j].second)
            {
                ti[j] = ti[t] + g[t][j].second;
                path_t[j].assign(path_t[t].begin(), path_t[t].end());   
                path_t[j].push_back(j);
            }
            else if(ti[j] == ti[t] + g[t][j].second)
                if(path_t[j].size() > path_t[t].size() + 1)
                { 
                    path_t[j].assign(path_t[t].begin(), path_t[t].end());   
                    path_t[j].push_back(j);
                } 

        }
    }
}

int main()
{
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);

    while(m --)
    {
        int v1, v2, one_way, length, t;
        cin >> v1 >> v2 >> one_way >> length >> t;

        if(one_way) g[v1][v2] = {length, t};
        else g[v1][v2] = g[v2][v1] = {length, t};
    }

    cin >> S >> T;

    dijkstra_dist();
    memset(st, 0, sizeof st);
    dijkstra_time();

    if(path_d[T] != path_t[T])
    {
        printf("Distance = %d: ", dist[T]);
        cout << path_d[T][0];
        for(int i = 1; i < path_d[T].size(); i ++) cout << " -> " << path_d[T][i];
        cout << endl;

        printf("Time = %d: ", ti[T]);
        cout << path_t[T][0];
        for(int i = 1; i < path_t[T].size(); i ++) cout << " -> " << path_t[T][i];
    }
    else
    {
        printf("Distance = %d; Time = %d: ", dist[T], ti[T]);
        cout << path_d[T][0];
        for(int i = 1; i < path_d[T].size(); i ++) cout << " -> " << path_d[T][i];
    }

    return 0;
}



JackFrost
16小时前
#include <iostream>
#include <cstring>
#include <unordered_map>
#include <vector>

using namespace std;

const int N = 210;

int g[N][N]; // 邻接矩阵
int dist[N], hap[N], av_hap[N], cnt[N], w[N]; // 最短路 幸福感 平均幸福感 最短路的数量 点权
bool st[N];
vector<int> path[N]; // 最短路的路径
unordered_map<string, int> map; // <城市,编号>
unordered_map<int, string> re_map; // <编号,城市>

int n, k;
string S,T = "ROM";

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0; hap[1] = 0; av_hap[1] = 0; cnt[1] = 1; path[1].push_back(1);

    for(int i = 1; i <= n; i ++)
    {
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;

        for(int j = 1; j <= n; j ++ )
        {
            if(dist[j] > dist[t] + g[t][j]) // 情况1:取最短路 更新dist hap path av_hap cnt
            {
                dist[j] = dist[t] + g[t][j];
                hap[j] = hap[t] + w[j];
                path[j] = path[t]; path[j].push_back(j);
                av_hap[j] = hap[j] / (path[j].size()-1);
                cnt[j] = cnt[t];
            }
            else if(dist[j] == dist[t] + g[t][j]) // 情况2:多个最短路相等 合并cnt 
            {
                cnt[j] += cnt[t];
                if(hap[j] < hap[t] + w[j]) // 情况3:取最大幸福感 更新hap path av_hap
                {
                    hap[j] = hap[t] + w[j];
                    path[j] = path[t]; path[j].push_back(j);
                    av_hap[j] = hap[j] / (path[j].size()-1);
                }
                else if(hap[j] == hap[t] + w[j]) 
                {
                    if(av_hap[j] < (hap[t] + w[j])/(path[t].size()-1+1)) // 情况4:取平均最大幸福感
                    {
                        path[j] = path[t]; path[j].push_back(j);
                        av_hap[j] = hap[j] / (path[j].size()-1);
                    }
                }
            }
        }
    }
}

int main()
{
    cin >> n >> k >> S;

    memset(g, 0x3f, sizeof g);

    map[S] = 1; re_map[1] = S; // 城市编号从1开始
    for(int i = 2; i <= n; i ++ )
    {
        string city;
        int a;
        cin >> city >> a;

        map[city] = i; re_map[i] = city;
        w[i] = a;
    }

    while(k --)
    {
        string a, b;
        int c;
        cin >> a >> b >> c;
        g[map[a]][map[b]] = g[map[b]][map[a]] = c;
    }

    dijkstra();

    cout << cnt[map[T]] << ' ' << dist[map[T]] << ' ' << hap[map[T]] << ' ' << av_hap[map[T]] << endl;

    cout << re_map[path[map[T]][0]];

    for(int i = 1; i < path[map[T]].size(); i ++) cout << "->" << re_map[path[map[T]][i]];

    return 0;
}


活动打卡代码 AcWing 1507. 旅行计划

JackFrost
20小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 510;

PII g[N][N]; // first 表示距离;second 表示花费
int dist[N], fee[N]; // 最短路 所有最短路中最小的花费
bool st[N];
vector<int> path[N]; // 所有最短路中最小的花费的路径
int n, m, S, T;

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0; fee[S] = 0; path[S].push_back(S);

    for(int i = 0; i < n; i ++ )
    {
        int t = -1;
        for(int j = 0; j < n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;

        for(int j = 0; j < n; j ++ )
        {
            if(dist[j] > dist[t] + g[t][j].first) // 情况1:取最小;更新dist fee path
            {
                dist[j] = dist[t] + g[t][j].first;
                fee[j] = fee[t] + g[t][j].second;
                path[j].assign(path[t].begin(),path[t].end()); 
                path[j].push_back(j);
            }
            else if(dist[j] == dist[t] + g[t][j].first) // 情况2: 相等;花费更小时更新fee path
            {
                if(fee[j] > fee[t] + g[t][j].second) 
                {
                    fee[j] = fee[t] + g[t][j].second;
                    path[j].assign(path[t].begin(),path[t].end()); 
                    path[j].push_back(j);
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m >> S >> T;
    memset(g, 0x3f, sizeof g);

    while(m --)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        g[a][b] = g[b][a] = {c, d};
    }

    dijkstra();

    for(auto ver : path[T]) cout << ver << ' ';
    cout << dist[T] << ' ' << fee[T];    

    return 0;
}



活动打卡代码 AcWing 1475. 紧急情况

JackFrost
21小时前

紧急情况.PNG

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N= 510;

int g[N][N];
int w[N]; // 各个结点的权值
int dist[N], cnt[N], sum[N]; // 最短路 最短路的数量 所有最短路中最大点权和
bool st[N];
int n, m, S,T;

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0; cnt[S] = 1; sum[S] = w[S];

    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 0; j < n; j ++ )
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;

        for(int j = 0; j < n; j ++)  // 对dijkstra 进行扩展
        {
            if(dist[j] > dist[t] + g[t][j]) // 情况1:取最小dist cnt sum
            {
                dist[j] = dist[t] + g[t][j];
                cnt[j] = cnt[t];
                sum[j] = sum[t] + w[j];
            }
            else if(dist[j] == dist[t] + g[t][j]) // 情况2:合并cnt sum
            {
                cnt[j] += cnt[t];
                sum[j] = max(sum[j], sum[t] + w[j]);
            }
        }
    }
}


int main()
{
    cin >> n >> m >> S >> T;
    for(int i = 0; i < n; i ++) cin >> w[i];
    memset(g, 0x3f, sizeof g);

    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    dijkstra();

    cout << cnt[T] << ' ' << sum[T];

    return 0;
}




捕获.PNG

捕获2.PNG

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 150010;

int h[N], e[N], ne[N], v[N], idx; // 稠密图用邻接表存储
int dist[N];
bool st[N];
int n, m;

void add(int id, int x, int w)
{
    e[idx] = x; v[idx] = w; ne[idx] = h[id]; h[id] = idx; idx ++;
}

int dijkstra() // 堆优化 O(mlogn)
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    priority_queue<PII,vector<PII>,greater<PII>> heap; // 存储没有确定最短路的那些点
    heap.push({0,1}); // 初始化

    while(heap.size())
    {
        auto t = heap.top(); // 在堆中找到距离最近的那个点
        heap.pop();
        int d = t.first, id = t.second;

        if(st[id]) continue; // 如果是冗余,则跳过
        st[id] = true; // 否则将其加入集合S(已经确定最短路的点)

        for(int i = h[id]; ~i; i = ne[i]) // 用距离d更新其他点到源点的最短距离
        {
            int j = e[i];
            if(dist[j] > d + v[i])
            {
                dist[j] = d + v[i];
                heap.push({dist[j], j});
            }
        }
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);

    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    int t = dijkstra();
    cout << t << endl;
    return 0;
}



思路

浅析dijskra算法(含dijskra算法队列优化和链式前向星存图)
为什么无穷大总是0x3f3f3f3f而不是0x7fffffff?

捕获.PNG

// O(n^2)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;

int g[N][N]; // 邻接矩阵存储图(最好是稠密图,邻接表适合存储稀疏图)
int n, m;
int dist[N]; // 结点1到结点i的最短路为dist[i]
bool st[N]; // st[i]为true 表示结点i已经找到最短路

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist); // 初始最短距离为无穷大
    dist[1] = 0; // 结点1到1的距离为0

    for(int i = 0; i < n; i ++) // 循环n次,每次确定一个点到源点的最短路
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ ) // 在没有确定最短路的结点中找到最短t
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true; // 将t 加入 S

        for(int j = 1; j <= n; j ++ ) // 用t更新,其他结点到源点的距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;

    memset(g, 0x3f, sizeof g); // 去除自环

    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;

        g[a][b] = min(g[a][b], c); // 去除重边
    }

    int t = dijkstra();

    cout << t << endl;

    return 0;
}


活动打卡代码 AcWing 1584. 最大的一代

DFS

/*
用邻接矩阵存储家谱树
dfs搜索家谱树,记录最大层数,以及每一层的结点数量

*/
#include <iostream>

using namespace std;

const int N = 110;

bool g[N][N];
int n, m;
int cnt[N];
int max_depth;

void dfs(int u, int depth)
{
    cnt[depth] ++ ;

    if(depth > max_depth) max_depth = depth;

    for(int i = 1; i <= n; i ++)
        if(g[u][i]) dfs(i, depth + 1);
}

int main()
{
    cin >> n >> m;

    while(m --)
    {
        int id, k;
        cin >> id >> k;
        while(k --)
        {
            int son;
            cin >> son;
            g[id][son] = true;
        }
    }

    dfs(1, 1);

    int depth = 0, max_cnt = 0;

    for(int i = 1; i <= max_depth; i ++)
        if(cnt[i] > max_cnt) 
        {
            depth = i;
            max_cnt = cnt[i];
        }

    cout << max_cnt << ' ' << depth;

    return 0;
}

BFS

/*
用邻接矩阵存储家谱树
bfs 层序遍历每一层,同时记录每一层的结点数
*/
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

bool g[N][N];
int n, m;
int cnt[N], max_depth;
int q[N];

void bfs(int root)
{
    int hh = 0, tt = 0;
    q[0] = root;

    int depth = 0;
    while(hh <= tt)
    {
        int head = hh, tail = tt;
        depth ++;
        while(hh <= tail)
        {
            int t = q[hh ++];
            cnt[depth] ++;
            for(int i = 1; i <= n; i ++ )
                if(g[t][i]) q[++ tt] = i;
        }
    }

    max_depth = depth;
}

int main()
{
    cin >> n >> m;

    while(m --)
    {
        int id, k;
        cin >> id >> k;
        while(k --)
        {
            int son;
            cin >> son;
            g[id][son] = true;
        }
    }

    bfs(1);

    int depth = 0, max_cnt = 0;

    for(int i = 1; i <= max_depth; i ++)
        if(cnt[i] > max_cnt) 
        {
            depth = i;
            max_cnt = cnt[i];
        }


    cout << max_cnt << ' ' << depth;

    return 0;
}

Vector 实现BFS

/*
用邻接矩阵存储家谱树
bfs 层序遍历每一层,同时记录每一层的结点数
*/
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

bool g[N][N];
int n, m;
vector<int> level[N];
int max_level;

void bfs(int root)
{
    int k = 1;
    level[1].push_back(root);

    while(level[k].size())
    {
        for(auto ver : level[k])
        {
            for(int i = 1; i <= n; i ++)
                if(g[ver][i]) level[k + 1].push_back(i);
        }
        k ++;
    }

    int l = 1;
    for(int i = 1; i < k; i ++ )
        if(level[i].size() > level[l].size())
            l = i;
    max_level = l;
}

int main()
{
    cin >> n >> m;

    while(m --)
    {
        int id, k;
        cin >> id >> k;
        while(k --)
        {
            int son;
            cin >> son;
            g[id][son] = true;
        }
    }

    bfs(1);

    cout << level[max_level].size() << ' ' << max_level; 

    return 0;
}


活动打卡代码 AcWing 1539. 等重路径

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 110;

bool g[N][N]; // 邻接矩阵存储多叉树
int w[N]; // 每个结点的权值
vector<vector<int>> res; // 存储所有路径, vector可以按字典序将所有路径排序
int n, m, S;

/*
有n的结点,m个内部结点
叶子结点数为n-m,从根结点到叶子结点的路径总数为n-m

从根结点搜向每一个叶子结点,记录路径权重,以及每一条路径包含的结点
*/
void dfs(int u, int s, vector<int>& p)
{
    bool is_left = true;
    for(int i = 0; i < n; i ++) // 判断节点 u 是否为叶结点
        if(g[u][i])
        {
            is_left = false;
            break;
        }

    if(is_left) // 如果是叶结点,表示已经搜到一条路径
    {
        if(s == S) res.push_back(p);
    }
    else // 如果不是叶结点,则递归搜索该结点的每一个孩子
    {
        for(int i = 0; i < n; i ++)
        {
            p.push_back(w[i]);
            if(g[u][i]) dfs(i, s + w[i], p);
            p.pop_back(); // 恢复现场
        }
    }

}

int main()
{
    cin >> n >> m >> S;

    for(int i = 0; i < n; i ++) cin >> w[i];

    for(int i = 0; i < m; i ++ ) // 构建邻接矩阵
    {
        int id, k;
        cin >> id >> k;
        while(k --)
        {
            int son;
            cin >> son;
            g[id][son] = true;
        }
    }

    vector<int> path({w[0]});

    dfs(0, w[0], path);

    sort(res.begin(), res.end(), greater<vector<int>>());

    for(auto p : res)
    {
        cout << p[0];
        for(int i = 1; i < p.size(); i ++) cout << ' ' << p[i];
        cout << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1628. 判断红黑树

/*
1. 根结点为黑色
2. 红色结点的孩子结点为黑色
3. 任意一个结点到每一个叶子结点的所有路径上的黑色结点数目相同( => 该结点的左右子树包含黑色结点数相同)

以上三个条件在构建二叉树的过程中判定

*/
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 40;

int pre[N], in[N];
unordered_map<int, int> pos;

bool res;

int build(int il, int ir, int pl, int pr, int& sum) // 前序遍历和中序遍历构建二叉树
{
    int root = pre[pl];
    int k = pos[abs(root)]; // 注意取绝对值

    if(k < il || k > ir) // 判断是否可以构成二叉搜索树
    {
        res = false;
        return 0;
    }

    int left = 0, right = 0; // 该结点的左右孩子初始化为黑色
    int ls = 0, rs = 0; // 左右两个子树到叶结点路径上黑色结点数
    if(il < k) left = build(il, k-1, pl + 1, pl + 1 + k-1-il, ls);
    if(k < ir) right = build(k+1, ir, pl + 1 + k-1-il+1, pr, rs);

    if(ls != rs) res = false; 
    sum = ls;

    if(root < 0)  // 该结点是红色
    {
        if(left < 0 || right < 0) res = false; // 两个孩子必须为黑色
    }
    else sum ++; // 如果为黑色

    return root;
}

int main()
{
    int T;
    cin >> T;

    while(T --)
    {
        int n;
        cin >> n;
        for(int i = 0; i < n; i ++) 
        {
            cin >> pre[i];
            in[i] = abs(pre[i]); // 取绝对值
        }

        sort(in, in + n);

        pos.clear();
        for(int i = 0; i < n; i ++) pos[in[i]] = i;

        int sum = 0;
        res = true;
        int root = build(0, n-1, 0, n-1, sum);

        if(root < 0) res = false; // 根必须为黑色
        if(res) puts("Yes");
        else puts("No");
    }

    return 0;
}




1552. AVL树的根
1600. 完全二叉树
1497. 树的遍历

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 40;

int l[N], r[N], v[N], h[N], idx;
int q[N];
int maxk;

void update(int u)
{
    h[u] = max(h[l[u]], h[r[u]]) + 1;    
}

void R(int& u)
{
    int p = l[u];
    l[u] = r[p]; r[p] = u;
    update(u); update(p);
    u = p;
}

void L(int& u)
{
    int p = r[u];
    r[u] = l[p]; l[p] = u;
    update(u); update(p);
    u = p;
}

int get_balance(int u)
{
    return h[l[u]] - h[r[u]];
}

void insert(int& u, int w)
{
    if(!u) u = ++ idx, v[u] = w;
    else if(w < v[u])
    {
        insert(l[u], w);
        if(get_balance(u) == 2)
        {
            if(get_balance(l[u]) == 1) R(u);
            else L(l[u]), R(u);
        }
    }
    else 
    {
        insert(r[u], w);
        if(get_balance(u) == -2)
        {
            if(get_balance(r[u]) == -1) L(u);
            else R(r[u]), L(u);
        }
    }
    update(u);
}

void bfs(int root)
{
    int hh = 0, tt = 0;
    q[0] = root;

    while(hh <= tt)
    {
        int t = q[hh ++];
        if(l[t]) q[++ tt] = l[t];
        if(r[t]) q[++ tt] = r[t];
    }
}

void dfs(int u, int k)
{
    if(u == 0) return ;
    if(k > maxk) maxk = k;
    dfs(l[u], k*2);
    dfs(r[u], k*2 + 1);
}

int main()
{
    int n;
    cin >> n;

    int root = 0;
    for(int i = 0; i < n; i ++)
    {
        int w;
        cin >> w;
        insert(root, w);
    }

    bfs(root);
    dfs(root, 1);

    cout << v[q[0]];
    for(int i = 1; i < n; i ++) cout << ' ' << v[q[i]];

    cout << endl;
    if(maxk == n) puts("YES");
    else puts("NO");

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 40;

int l[N], r[N], v[N], h[N], idx;
int q[N], pos[N];
int n;

void update(int u)
{
    h[u] = max(h[l[u]], h[r[u]]) + 1;    
}

void R(int& u)
{
    int p = l[u];
    l[u] = r[p]; r[p] = u;
    update(u); update(p);
    u = p;
}

void L(int& u)
{
    int p = r[u];
    r[u] = l[p]; l[p] = u;
    update(u); update(p);
    u = p;
}

int get_balance(int u)
{
    return h[l[u]] - h[r[u]];
}

void insert(int& u, int w)
{
    if(!u) u = ++ idx, v[u] = w;
    else if(w < v[u])
    {
        insert(l[u], w);
        if(get_balance(u) == 2)
        {
            if(get_balance(l[u]) == 1) R(u);
            else L(l[u]), R(u);
        }
    }
    else 
    {
        insert(r[u], w);
        if(get_balance(u) == -2)
        {
            if(get_balance(r[u]) == -1) L(u);
            else R(r[u]), L(u);
        }
    }
    update(u);
}

bool bfs(int root) // 层序遍历;按完全二叉树的方式,记录每个结点的位置信息
{
    int hh = 0, tt = 0;
    q[0] = root;
    pos[root] = 1; // 1

    int res = true;
    while(hh <= tt)
    {
        int t = q[hh ++];

        if(pos[t] > n) res = false; // 2

        if(l[t]) q[++ tt] = l[t], pos[l[t]] = pos[t] * 2; // 3
        if(r[t]) q[++ tt] = r[t], pos[r[t]] = pos[t] * 2 + 1; // 4
    }

    return res;
}

int main()
{
    cin >> n;

    int root = 0;
    for(int i = 0; i < n; i ++)
    {
        int w;
        cin >> w;
        insert(root, w);
    }

    bool res = bfs(root);


    cout << v[q[0]];
    for(int i = 1; i < n; i ++) cout << ' ' << v[q[i]];

    cout << endl;
    if(res) puts("YES");
    else puts("NO");

    return 0;
}