7、贝尔曼福特算法,是按顺序一轮一轮的松弛,如果有可以松弛的那就再来一轮;这个题第二轮就没有可以松弛的了,所以就没有第3轮了
8、这题是dijkstra算法,算法逻辑是:
Dijkstra 最短路径算法的步骤如下: 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; }View Code
[魔法]
【算法分析】 这题可以看成 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; }View Code
[方格取数]
【算法分析】 如果没有位置封锁,用 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; }View Code
没作业
标签:12,int,U6,cin,C++,算法,maxn,节点,dp From: https://www.cnblogs.com/jayxuan/p/18134052