C++U6-12-阶段复习测评

 

 

 

 

 

 

7、贝尔曼福特算法，是按顺序一轮一轮的松弛，如果有可以松弛的那就再来一轮；这个题第二轮就没有可以松弛的了，所以就没有第3轮了

 

8、这题是dijkstra算法，算法逻辑是：

Dijkstra 最短路径算法的步骤如下：

1. 初始化：创建一个距离数组 dist，用于存储起点到每个节点的初始估计距离，将其初始化为无穷大；创建一个前驱节点数组 pred，用于记录每个节点的前一个节点。
2. 标记起点：将起点标记为已访问，并将其距离设置为 0。
3. 选择未访问节点：从剩余未访问节点中选择距离最小的节点。
4. 更新距离：对选择的节点，更新其邻居节点的距离值。
5. 重复步骤 3 和 4，直到所有节点都被访问。
6. 根据前驱节点数组 pred 回溯得到最短路径。

Dijkstra 算法通过不断选择距离最小的未访问节点，并更新其邻居节点的距离，最终找到起点到其他节点的最短路径。

 

 

 

 

 

【算法分析】
采用邻接矩阵存图，a 
i,j
​=1 表示 i 和 j 之间有边。然后每次从一个没有访问过的点开始 dfs（也可以 bfs），将所有到达的点进行标记，并同时用一个变量记录此次 dfs 访问了几个点，那么这个变量的值就是连通块的大小，取个 max 即可。【参考代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 9;
int a[maxn][maxn];
bool vis[maxn];
int num, n, m;
void dfs(int x) {num++;vis[x] = 1;for (int i = 1; i <= n; i++) {if (a[x][i] && !vis[i]) dfs(i);}
}
int main() {cin >> n >> m;for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;a[u][v] = a[v][u] = 1;}int ans = 0;for (int i = 1; i <= n; i++) {if (!vis[i]) {num = 0;dfs(i);ans = max(ans, num);}}cout << ans;return 0;
}

 

 

[魔法]

 

 

 

 

【算法分析】
这题可以看成 n 个点，m 条边的有向图，每条边的权值是 1，求 x 到 y 的最短路径，由于 n 很小，可以使用 floyd(当然也可以使用 bfs（因为每条边的边权相同）、任何最短路径算法(题目数据范围很小))。【参考代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 9; 
int dp[maxn][maxn];
int main() {int n, m;cin >> n >> m;memset(dp, 0x3f, sizeof(dp));for (int i = 1; i <= n; i++) dp[i][i] = 0;for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;dp[u][v] = 1;}int x, y;cin >> x >> y;for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);}}}if (dp[x][y] < 0x3f3f3f3f) cout << dp[x][y];else cout << -1;return 0;
}

 

 

 

[方格取数]

 

 

【算法分析】
如果没有位置封锁，用 dp 
i,j
​表示从 (1,1) 到 (i,j) 的路径最大和，则状态转移方程为 dp 
i,j
​=max(dp 
i−1,j
​,dp 
i,j−1
​)+a 
i,j
​(a 
i,j
​表示方格 (i,j) 位置的数字)。现在考虑被封锁的情况，其实就是不能计算被封锁位置的 dp 值。最后不能到达 B，就是 dp 
i,j
​的值为 0。注意答案会爆 int。【参考代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 9; 
long long dp[maxn][maxn];
int a[maxn][maxn];
bool vis[maxn][maxn];
int main() {int n, k;cin >> n >> k;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) cin >> a[i][j];}for (int i = 0; i < k; i++) {int x, y;cin >> x >> y;vis[x][y] = 1;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (vis[i][j]) continue;if (i == 1 && j == 1) {dp[1][1] = a[1][1];continue;}if (dp[i - 1][j] || dp[i][j - 1]) {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];}}}cout << dp[n][n];return 0;
}

 

 

没作业