2023 算法设计与分析 （计算机与网安）第三次实验课
目录
1. BFS试炼之微博转发
2. DFS试炼之不同路径数
3. 并查集试炼之合并集合
4. 堆排序
5. 厦大GPA
6. 消防安全指挥问题
7. 铺设光纤问题
8. CCF A会报告
9. 商店 （挑战题）
1. BFS试炼之微博转发
Tag：bfs
存储：邻接表
思路：有搜索层数限制，用dist数组记录层数，超出要求则continue
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;const int N = 1005;
int n, l;
int e[N], ne[N], h[N], idx, dist[N];
bool st[N];
queue<int> q;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}int bfs(int x) {memset(st, 0, sizeof st);memset(dist, 0, sizeof dist);q.push(x);st[x] = true;int cnt = 0;while (q.size()) {auto t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i]; //cout << j << endl;if (st[j]) continue;dist[j] = dist[t] + 1;if (dist[j] > l) continue;++ cnt;q.push(j);st[j] = true;}}return cnt;
}int main() {memset(h, -1, sizeof h);cin >> n >> l;for (int i = 1; i <= n; ++ i) {int num, x;cin >> num;for (int j = 0; j < num; ++ j) {cin >> x;add(x, i);// cout << x << ' ' << i << endl;}}int t;cin >> t;while (t --) {int x;cin >> x;cout << bfs(x) << endl;}return 0;
}2. DFS试炼之不同路径数
Tag：dfs，字符串哈希
思路：以每个点为起点dfs搜索。用字符串哈希记录不重复路径数。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_set>
using namespace std;const int N = 7;
char g[N][N];
bool st[N][N];
int n, m, k, ans;
unordered_set<string> s;
char str[10];void dfs(int x, int y, int u) {if (u > k) {//cout << str << endl;if (!s.count(str)) {s.insert(str);++ ans;}return;}st[x][y] = true;str[u] = g[x][y];//cout << u << ' ' << str << endl;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};for (int i = 0; i < 4; ++ i) {int xx = x + dx[i], yy = y + dy[i];if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;dfs(xx, yy, u + 1);}
}int main() {cin >> n >> m >> k;for (int i = 0; i < n; ++ i)for (int j = 0; j < m; ++ j)cin >> g[i][j];for (int i = 0; i < n; ++ i) {for (int j = 0; j < m; ++ j) {memset(st, 0, sizeof st);dfs(i, j, 0);}}cout << ans << endl;return 0;
}3. 并查集试炼之合并集合
Tag: 并查集
思路：模板题
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;const int N = 1e5 + 5;
int p[N];
int n, m;int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);
}int main() {cin >> n >> m;for (int i = 1; i <= n; ++ i) p[i] = i;while (m --) {char c;int x, y;cin >> c >> x >> y;if (c == 'M') {if (find(x) != find(y)) p[find(x)] = find(y);} else {if (find(x) == find(y)) puts("Yes");else puts("No");}}return 0;
}4. 堆排序
略。用sort混过去了。
5. 厦大GPA
Tag：分组背包、（贪心）
思路：
绩点是价值，分数是体积，总分是容积。
分组背包问题，4组，每组可以取一个分数。
(前置处理写麻烦了，贪心只用每个档的最低分数数据就可以了)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;//绩点是价值 分数是体积 总分是容积
//分组背包问题 4组 每组可以取一个分数const int N = 405;
int v[N], w[N];
int f[N];void init() {for (int i = 1, s = 0; s <= 100;) {switch (s) {case 0:for (; s <= 59; ++i, ++s) v[i] = s, w[i] = 0;break;case 60:for (; s <= 63; ++i, ++s) v[i] = s, w[i] = 10;break;case 64:for (; s <= 67; ++i, ++s) v[i] = s, w[i] = 17;break;case 68:for (; s <= 71; ++i, ++s) v[i] = s, w[i] = 20;break;case 72:for (; s <= 74; ++i, ++s) v[i] = s, w[i] = 23;break;case 75:for (; s <= 77; ++i, ++s) v[i] = s, w[i] = 27;break;case 78:for (; s <= 80; ++i, ++s) v[i] = s, w[i] = 30;break;case 81:for (; s <= 84; ++i, ++s) v[i] = s, w[i] = 33;break;case 85:for (; s <= 89; ++i, ++s) v[i] = s, w[i] = 37;break;case 90:for (; s <= 100; ++i, ++s) v[i] = s, w[i] = 40;break;}}
}int main() {init();
//for(int i=1; i<=101; ++ i) printf("%d %d\\n", v[i], w[i]);int m;while (cin >> m) {memset(f, 0, sizeof f);for (int i = 1; i <= 4; ++ i) {for (int j = m; j >= 0; -- j) {for (int k = 1; k <= 101; ++ k)if (v[k] <= j)f[j] = max(f[j], f[j - v[k]] + w[k]);//cout << f[i][j] << endl;}}double res = f[m] / 10.0;//cout << res << endl;printf("%.1f\\n", res);}return 0;
}
6. 消防安全指挥问题
Tag：dijkstra
思路：对消防队在的位置为起点dijkstra，比较取最短。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;const int N = 1005;
int xfd[N];
int n, m, p, q;
int g[N][N], dist[N];
bool st[N];int dijkstra(int x) {memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[x] = 0;//cout << m << endl;for (int i = 0; i < m; ++ i) {int t = -1, dis = 0x3f3f3f3f;for (int j = 1; j <= m; ++ j) {if (!st[j] && (t == -1 || dist[j] < dis)) {t = j;dis = dist[j];}}
//cout << t << endl;st[t] = true; if (t == q) return dist[q];for (int i = 1; i <= m; ++ i) dist[i] = min(dist[i], dist[t] + g[t][i]);}return 0x3f3f3f3f;
}int main() {int t;cin >> t;while (t --) {cin >> n >> m >> p >> q; memset(g, 0x3f, sizeof g);for (int i = 0; i < n; ++i) cin >> xfd[i];while (p --) {int a, b, w;cin >> a >> b >> w;g[a][b] = g[b][a]= min(g[a][b], w);}int ans = 0x3f3f3f3f;for (int i = 0; i < n; ++ i) {//cout <<m << endl;ans = min(ans, dijkstra(xfd[i]));//cout << ans << endl;}cout << ans << endl;}return 0;
}
7. 铺设光纤问题
Tag：prim
思路：模板题。纳入未标记的离现有的一团点距离最近的点。dist存的是到当前这团点的距离。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;const int N = 105;
int g[N][N], dist[N];
int n, ans;
bool st[N];void prim() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < n; ++ i) {int dis = 0x3f3f3f3f, t;for (int j = 1; j <= n; ++ j) {if (!st[j] && dist[j] < dis) {dis = dist[j];t = j;}}st[t] = true;ans += dist[t];for (int i = 1; i <= n; ++i) dist[i] = min(dist[i], g[t][i]);}
}int main() {cin >> n;for (int i = 1; i <= n; ++ i)for (int j = 1; j <= n; ++ j)cin >> g[i][j];prim();cout << ans << endl;return 0;
}8. CCF A会报告
Tag：多重背包
思路：模板题。除种类体积外，再循环每个品类的个数。注意判是否小于等于容积。
拓展：如果s[]的范围增大，则可以考虑二进制打包优化。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;const int N = 6005;
int v[N], w[N], s[N];
int n, m;
int f[N];int main() {cin >> n >> m;for (int i = 1; i <= n; ++ i) {cin >> v[i] >> w[i] >> s[i];}for (int i = 1; i <= n; ++ i) {for (int j = m; j >= v[i]; -- j) {for (int k = 1; k <= s[i]; ++ k) {if (k * v[i] <= j)f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);}}}cout << f[m] << endl;return 0;
}9. 商店 （挑战题）
Tag：贪心
存储：优先队列小根堆
思路：
贪心：为了满足尽可能多的预订单，每次应优先处理商品数少的订单
又因为当天的货物只可以被当天的订单和后续的订单消耗，所以可以倒序处理数据
核心：用当前的供应量增序处理队列中的剩余订单
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;#define out first
#define index second
typedef pair<int, int> PII;
const int N = 3e5 + 5;
priority_queue<PII, vector<PII>, greater<PII> > q;
int in[N], out[N];
int n, res;int main() {cin >> n;for (int i = 1; i <= n; ++ i) cin >> in[i] >> out[i];for(int i=n; i; --i){int cur = in[i];q.push({out[i], i});while(q.size()){auto t = q.top();q.pop();int csm = min(t.out, cur);cur -= csm;t.out -= csm;if(t.out == 0) ++ res;else q.push(t);if(cur == 0) break;}}cout << res << endl;return 0;
}