吉林大学计算机23级数据结构上机实验（第八周）
A 快速排序
给定包含n个元素的整型数组a[1],a[2],...,a[n]，利用快速排序算法对其进行递增排序，请输出排序过程，即每次Partition之后的数组。最后输出排序后的数组。每次选择所处理的子数组的第一个元素作为基准元素。
输入格式:
输入为两行，第一行为一个整数n（1<n≤1000），表示数组长度。第二行为n个空格间隔的整数，表示待排序的数组。
输出格式:
输出为若干行，每行依次输出Partition后的整个数组，每个元素后一个空格。最后一行输出排序后的数组。
输入样例:
5 4 5 3 2 1输出样例:
2 1 3 4 5 1 2 3 4 5 1 2 3 4 5提示:
就是在每次调用完Partition函数后输出R[1]….R[n]。其余与快速排序一致。
背一个快排模板。。
#include <bits/stdc++.h> using namespace std; const int N = 1010; int a[N]; int n; void quicksort(int l, int r) { if (l >= r) { return; } int x = a[l]; int i = l, j = r + 1; while (i < j) { do i++; while (i <= r && a[i] <= x); do j--; while (a[j] > x); if (i < j) { swap(a[i], a[j]); } } swap(a[l], a[j]); for (int i = 1; i <= n; i++) { cout << a[i] << " "; }cout << endl; quicksort(l, j - 1); quicksort(j + 1, r); } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } quicksort(1, n); for (int i = 1; i <= n; i++) { cout << a[i] << " "; } cout << endl; return 0; }
B 网络布线
亚洲杯赛期间需要保证运动员公寓网络畅通，以使运动员都能正常上网。
假定公寓楼内有n个房间，编号为0…n−1，每个房间都需要网络连接。房间 i 有网络，当且仅当满足如下2个条件之一：（1）房间 i 安装了路由器（成本为 ri>0）
（2）房间 i 和房间 j 有网线连接且房间 j 有网络（在房间 i 和房间 j 之间布置网线的成本为 fij>0）
假定你是赛事组委会的网络工程师，请编写程序设计一个网络布线方案（哪些房间安装路由器，哪些房间之间布置网线），使得所有房间都有网络，且总成本最小。
例如下图包含7个房间和10个可能的连接，安装路由器的成本为括号内数字，房间之间布置网线的成本为边的权值。其解决方案为右下图，即在房间1和4安装路由器，并进行图中的网线布置。总成本为120。
输入格式:
输入第一行为两个正整数n和e；n为房间数，不超过600；e为可能的连接数，不超过2×105。接下来一行为n个空格间隔的正整数，第i个整数(i≥0)表示在房间i安装路由器的成本。接下来e行，每行为3个非负整数i、j、f，表示在房间i和房间j之间布置网线的成本为f。
输出格式:
输出为一个整数，表示最优网络布线方案的成本。
输入样例:
7 10 60 10 35 55 40 70 70 0 1 20 0 4 75 0 3 45 1 3 50 1 2 15 2 6 5 5 6 45 4 5 5 3 5 25 3 6 65输出样例:
120提示:
可引入一个虚拟顶点，将该顶点与其他所有顶点用边相连，边权等于那些顶点的权值。进而形成一个新图，对新图求最小支撑树。注意本题顶点编号从0开始。
超级源点的最小生成树。。
注意如果用cin输入时记得加开关。。不然会超时。如果不想加那么用scanf就好了。
这里给出kruskal和prim的两种做法。
kruskal：
#include<bits/stdc++.h> using namespace std; const int N = 3e5 + 10; int p[N]; int n, m; int ans; struct edge { int a, b, w; bool operator<(edge& W) { return w <W. w; } }e[N]; int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } void solve() { cin >> n >> m; for (int i = 0;i <= n;i++) { p[i] = i; } int cnt = 0; for (int i = 1;i <= n;i++) { int k; cin >> k; cnt++; e[cnt].a = i - 1; e[cnt].b = n; e[cnt].w = k; } for (int i = 1;i <= m;i++) { int a, b, c; cin >> a >> b >> c; cnt++; e[cnt].a = a; e[cnt].b = b; e[cnt].w = c; } sort(e + 1, e + cnt+1); for (int i = 1;i <= cnt;i++) { //cout << e[i].w << endl; int x = find(e[i].a); int y = find(e[i].b); if (x != y) { ans += e[i].w; p[x] = y; } } cout << ans; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); return 0; }prim：
#include<bits/stdc++.h> using namespace std; const int N=650,M = 3e5 + 10; int h[N], e[M], w[M], ne[M], idx; int dist[N], st[N]; int n, m; int ans; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } void prim() { memset(st, 0, sizeof st); memset(dist, 0x3f, sizeof dist); dist[0] = 0; //cout << 1 << endl; for (int i = 0; i <= n; i++) { int t = -1; //cout << 1 << endl; for (int j = 0; j <= n; j++) { if (!st[j] && (t == -1 || dist[j] < dist[t])) { t = j; } } st[t] = 1; ans += dist[t]; for (int j = h[t]; ~j; j = ne[j]) { int k = e[j]; if (w[j] < dist[k]) { dist[k] = w[j]; } } } } void solve() { cin >> n >> m; memset(h, -1, sizeof h); int cnt = 0; for (int i = 0; i < n; i++) { int k; cin >> k; add(n, i, k); add(i, n, k); } for (int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; add(a, b, c); add(b, a, c); } //cout << 1 << endl; prim(); cout << ans; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); return 0; }堆优化后的prim：
#include<bits/stdc++.h> using namespace std; const int N=650,M = 3e5 + 10; int h[N], e[M], w[M], ne[M], idx; int dist[N], st[N]; int n, m; int ans; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } void prim() { memset(st, 0, sizeof st); memset(dist, 0x3f, sizeof dist); q.push({ 0, 0 }); dist[0] = 0; while (q.size()) { auto t = q.top(); q.pop(); int ver = t.second, distance = t.first; if (st[ver]) { continue; } st[ver] = 1; ans += distance; for (int i = h[ver]; ~i; i = ne[i]) { int j = e[i]; if (dist[j] > w[i]) { dist[j] = w[i]; q.push({ dist[j], j }); } } } } void solve() { cin >> n >> m; memset(h, -1, sizeof h); int cnt = 0; for (int i = 0; i < n; i++) { int k; cin >> k; add(n, i, k); add(i, n, k); } for (int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; add(a, b, c); add(b, a, c); } //cout << 1 << endl; prim(); cout << ans; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); return 0; }
C 最大边
给定一个包含n个顶点的无向正权连通图，顶点编号为1到n。请编写程序计算其最小支撑树中任意两个顶点间路径中，权值最大的边的权值。
输入格式:
第一行为2个正整数n和m，n为图中顶点个数，m为边的条数。接下来m行，每行3个整数a、b、c，表示顶点a和顶点b之间有一条权值为c的边。随后一行为一个正整数T，表示查询数目。接下来T行，每行2个整数a和b，表示查询最小支撑树中顶点a和b间路径中的最大边。n≤2000，m≤30000，1 ≤a,b≤ n且a=b，c ≤65535，T ≤ 1000 。
输出格式:
对于每个查询输出一行，为1个整数，表示最小支撑树两个顶点间的路径中的最大边的权值。
输入样例:
8 20 2 7 44181 1 2 36877 3 6 2506 2 8 46829 7 1 2843 4 5 40699 1 3 15911 7 6 15553 5 6 22541 8 6 62008 3 4 62009 5 7 53337 5 3 12157 4 6 10112 1 5 22574 3 7 28993 4 7 53536 6 1 951 4 2 31411 7 8 31020 10 7 5 5 4 4 2 7 2 3 4 1 5 1 5 7 3 6 1 4 1输出样例:
12157 12157 31411 31411 10112 12157 12157 2843 951 10112
这个题没有用标准的解法，暴力搞的，不过也能过，凑合看吧，懒得写其他的了。
#include<bits/stdc++.h> using namespace std; const int N = 3e5 + 10, M = 2010; int h[M], e[N], ne[N], w[N], idx; int p[N]; int cnt[M]; int n, m, t; struct edge { int a, b, w; bool operator<(edge& W) { return w <W. w; } }ed[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } void bfs(int a, int b) { int res = 0; bool flag = 1; bool st[M]; memset(st, false, sizeof st); memset(cnt, 0, sizeof cnt); queue<int >q; q.push(a); while (q.size()) { //cout << 1 << endl; int v = q.front(); q.pop(); if (st[v]) { continue; } st[v] = true; for (int i = h[v];~i;i = ne[i]) { int j = e[i]; if (st[j]) { continue; } cnt[j] = max(cnt[v], w[i]); //cout << w[i] << endl; q.push(j); } } } void solve() { cin >> n >> m; memset(h, -1, sizeof h); for (int i = 0;i <= n;i++) { p[i] = i; } for (int i = 1;i <= m;i++) { int a, b, c; cin >> a >> b >> c; ed[i].a = a; ed[i].b = b; ed[i].w = c; } sort(ed + 1, ed + m+1); for (int i = 1;i <= m;i++) { //cout << ed[i].w << endl; int x = find(ed[i].a); int y = find(ed[i].b); if (x != y) { p[x] = y; add(ed[i].a, ed[i].b, ed[i].w); add(ed[i].b, ed[i].a, ed[i].w); } } cin >> t; while (t--) { int a, b; cin >> a >> b; bfs(a, b); cout << cnt[b] << endl; } } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); return 0; }
原文地址：https://blog.csdn.net/2301_80221401/article/details/144376051
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！