有基础班_day04课上题目

zxcvbnm

2025-07-04 15:31:47

发布于：上海

15阅读

0回复

0点赞

题目
有向图的邻接矩阵存储
邻接表存储带权图
邻接矩阵存储带权图
图中结点的度
猴子选大王

有向图的邻接矩阵存储

题目大意

给定一个包含 $N$ 个顶点、 $M$ 条边的有向图，要求将其以邻接矩阵的形式输出。

邻接矩阵定义：

$G[i][j] = 1$ 表示存在一条从点 $i$ 到点 $j$ 的有向边；
否则 $G[i][j] = 0$ 。

题意分析

输入：
- 第 $1$ 行：两个整数 $N, M$ ；
- 接下来的 $M$ 行，每行两个整数 $u, v$ ，表示一条有向边 $(u, v)$ ；
输出：
- 一个 $N \times N$ 的邻接矩阵 $G$ 。

解题思路

建立一个二维数组 $G[N+1][N+1]$ ；
对于每条边 $(u, v)$ ，设置 $G[u][v] = 1$ ；
遍历整个矩阵，按格式输出每一行。

时间复杂度分析

初始化矩阵： $O(N^2)$ ；
处理边： $O(M)$ ；
输出矩阵： $O(N^2)$ ；
总体时间复杂度为 $\boxed{O(N^2)}$ ，对 $N \le 100$ 完全可行。

C++ 代码实现

#include <iostream>
using namespace std;

int G[105][105]; // 邻接矩阵

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

    // 读入 M 条边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u][v] = 1; // 有向边：从 u 指向 v
    }

    // 输出邻接矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << G[i][j];
            if (j < n) cout << " ";
        }
        cout << '\n';
    }

    return 0;
}

邻接表存储带权图

题目大意

给定一个 有向带权图，图中共有 $N$ 个顶点、 $M$ 条边。每条边有一个权重。
请使用 邻接表（vector 数组） 存储图，并输出 所有边的权重之和。

题意分析

输入：
- 第 1 行：两个整数 $N, M$ 表示顶点数和边数；
- 接下来 $M$ 行，每行包含三个整数 $u, v, w$ ，表示有向边 $(u \to v)$ ，边权为 $w$ ；
输出：
- 所有边的权重之和。

解题思路

建立一个邻接表 vector<pair<int, int>> graph[N + 1]；
每读入一条边 $(u, v, w)$ $(u, v, w)$ ：
- 将 (v, w) 存入 graph[u]；
- 同时累计边权和；
最终输出权重和。

时间复杂度分析

建图过程遍历所有边： $O(M)$ ；
因此总时间复杂度为 $\boxed{O(M)}$ ，可轻松通过 $M \le 10^5$ 的测试数据。

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5 + 10;
vector<pair<int, int>> graph[N]; // 邻接表：graph[u] 存储所有 (v, w)

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

    long long total = 0;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        total += w;
    }

    cout << total << endl;
    return 0;
}

邻接矩阵存储带权图

题目大意

一个国家有 $n$ 个城市，通过 $m$ 条高速公路连接，每条公路有一个长度。
现在有 $q$ 个修建建议，每个建议是一条新公路（带权）。如果新公路 比原有同一对城市之间最短的直达距离更短，则认为有效，输出 Accepted，否则输出 Cancel。

题意分析

多条边可能存在（即重边），对同一对城市，只保留最短边；
对每个提议，判断是否能让某对城市的直接距离更短（不能经过其他城市）。

解题思路

建图（邻接矩阵）

建立一个二维数组 G[n+1][n+1]；
初始化 G[i][j] = inf，并设 G[i][i] = 0；
遍历所有边，若存在重边，只保留最短的那一条：
G[x][y] = G[y][x] = min(G[x][y], len)

处理提议

若当前提议的长度 $z$ 小于现有的 $G[x][y]$ ，说明新建会更优 → Accepted
否则 → Cancel
注意：题目说提议不改变图本身，所以不更新邻接矩阵。

时间复杂度分析

构建图： $O(m)$
每个查询判断： $O(1)$
总体时间复杂度： $\boxed{O(n^2 + q)}$

C++ 代码实现

#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1e9;
int G[105][105];

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

    // 初始化邻接矩阵
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            G[i][j] = (i == j ? 0 : INF);

    // 读入已有边，保留最短的
    for (int i = 0; i < m; i++) {
        int x, y, len;
        cin >> x >> y >> len;
        G[x][y] = G[y][x] = min(G[x][y], len);
    }

    // 处理每项提议
    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        if (z < G[x][y]) cout << "Accepted\n";
        else cout << "Cancel\n";
    }

    return 0;
}

图中结点的度

题目大意

给定一个 无向图，包含 $N$ 个结点和 $M$ 条边。
每条边连接两个结点 $u$ 和 $v$ ，代表它们之间有一条双向连边。
你的任务是，计算并输出 每个结点的度数，即它连接的边的数量。

题意分析

无向图的边 $(u, v)$ 对两个结点都产生影响；
每出现一次边，就让两个端点的度数分别加一；
结点编号是从 $1$ 开始的。

解题思路

建立一个数组 deg[i] 表示第 $i$ 个结点的度数；
读入每条边 $(u, v)$ $(u, v)$ 时：
- deg[u]++，deg[v]++
最后输出 $1$ 到 $N$ 所有顶点的度数。

时间复杂度分析

遍历 $M$ 条边，每条边仅更新两个度数；
总时间复杂度： $\boxed{O(M)}$
空间复杂度： $\boxed{O(N)}$ ，只存储度数。

C++ 代码实现

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int deg[N];

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

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
    }

    for (int i = 1; i <= n; i++) {
        cout << deg[i] << " ";
    }

    cout << endl;
    return 0;
}

猴子选大王

题目大意

$n$ 只猴子按编号 $1$ 到 $n$ 顺时针围成一圈，从 $1$ 号猴子开始报数，每次报到第 $m$ 个猴子就出圈。下一只猴子从 $1$ 开始重新报数，直到只剩下一只猴子，它就是大王。

输入两个整数 $n$ 和 $m$ ，输出大王的编号。

题意分析

这个问题是著名的 约瑟夫环问题。本题可使用链表结构模拟整个过程：

每只猴子用一个链表节点表示；
按编号顺序形成一个循环单链表；
每轮从当前位置走 $m-1$ 步，找到要出圈的猴子；
删除该猴子，继续下轮，直到只剩最后一只。

解题思路

定义链表结构 Node，包含猴子编号和指向下一个猴子的指针；
初始化 $n$ 个结点，连成一个循环单链表；
设置指针 p 指向要删除结点的前一个节点；
每次报数从 p 出发，向前走 $m-1$ 步；
删除第 $m$ 个结点，并继续下一轮；
重复直到 p->next == p（只剩一个结点）；
输出该猴子的编号。

时间复杂度分析

每轮删除 1 个猴子，共需 $n - 1$ 轮；
每轮最多走 $m$ 步，因此总复杂度为： $\boxed{O(n \cdot m)}$ ；
空间复杂度： $\boxed{O(n)}$ （动态分配 $n$ 个链表节点）。

C++代码实现

#include <iostream>
using namespace std;

// 定义链表结点
struct Node {
    int id;
    Node* next;
};

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

    // 构建循环链表
    Node* head = new Node;
    head->id = 1; head->next = NULL;
    Node* prev = head;
    for (int i = 2; i <= n; ++i) {
        Node* curr = new Node;
        curr->id = i; curr->next = NULL;
        prev->next = curr;
        prev = curr;
    }
    prev->next = head; // 收尾相连

    // p 指向要删除结点的前一个结点
    Node* p = prev;

    while (p->next != p) {
        // 报 m 个数，走 m-1 步
        for (int i = 1; i < m; ++i) {
            p = p->next;
        }
        Node* del = p->next;
        p->next = del->next;
        delete del; // 释放内存
    }

    // 输出最后剩下的大王编号
    cout << p->id << endl;
    delete p;
    return 0;
}