3 条题解
-
0
Choose Two and Eat One
#include <bits/stdc++.h> #define int long long using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 500; const int MAXM = 250000; int n, m; // n个点 m条边 int a[MAXN + 5]; int mod; struct Edge { int u, v, w; }; Edge e[MAXM + 5]; bool cmp(Edge a, Edge b) { return a.w > b.w; } int fa[MAXN + 5]; int findFa(int x) { if (x == fa[x]) return x; return fa[x] = findFa(fa[x]); } // a^b (mod p) long long quick_pow(long long a, long long b, long long p) { long long res = 1; while (b) { if (b & 1) res = (res * a) % p; b = b >> 1; a = (a * a) % p; } return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> mod; for (int i = 1; i <= n; i++) cin >> a[i]; int eCnt = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i != j) { eCnt++; e[eCnt].u = i; e[eCnt].v = j; e[eCnt].w = (quick_pow(a[i], a[j], mod) + quick_pow(a[j], a[i], mod)) % mod; } m = eCnt; // 排序 sort(e + 1, e + m + 1, cmp); // 并查集初始化 for (int i = 1; i <= n; i++) fa[i] = i; // kruskal/避开环 int ans = 0; int cnt = 0; for (int i = 1; i <= m; i++) { // e[i].u <-> e[i].v : e[i].w // 如果会构成环，就不选，否则就选 int faU = findFa(e[i].u); int faV = findFa(e[i].v); if (faU != faV) { fa[faU] = faV; ans += e[i].w; cnt++; } } if (cnt == n - 1) cout << ans << "\n"; else cout << "orz\n"; return 0; } -
0
33DAI LV 5 (1/1) @ 2023-1-16 11:16:53
走廊泼水节
#include <bits/stdc++.h> using namespace std; int T; int n, m; // n个点 m条边 struct Edge { int u, v, w; }; Edge e[6005]; bool cmp(Edge a, Edge b) { return a.w < b.w; } int fa[6005]; int cnt[6005]; int findFa(int x) { if (x == fa[x]) return x; return fa[x] = findFa(fa[x]); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> T; while (T--) { cin >> n; m = n - 1; for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w; // 排序 sort(e + 1, e + m + 1, cmp); // 并查集初始化 for (int i = 1; i <= n; i++) fa[i] = i, cnt[i] = 1; // kruskal/避开环 int ans = 0; for (int i = 1; i <= m; i++) { // e[i].u <-> e[i].v : e[i].w // 如果会构成环，就不选，否则就选 int faU = findFa(e[i].u); int faV = findFa(e[i].v); // 把两个集合合并时，构成完全图，补充另外需要的边 int cntU = cnt[faU]; int cntV = cnt[faV]; int len = e[i].w; // 必须选择这条边作为最小生成树 ans += (cntU * cntV - 1) * (len + 1); // 合并两个集合 fa[faU] = faV; cnt[faV] += cnt[faU]; } cout << ans << "\n"; } return 0; } -
0
模板
Kruskal
#include <bits/stdc++.h> using namespace std; int n, m; // n个点 m条边 struct Edge { int u, v, w; }; Edge e[212345]; bool cmp(Edge a, Edge b) { return a.w < b.w; } int fa[5005]; int findFa(int x) { if (x == fa[x]) return x; return fa[x] = findFa(fa[x]); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w; // 排序 sort(e + 1, e + m + 1, cmp); // 并查集初始化 for (int i = 1; i <= n; i++) fa[i] = i; // kruskal/避开环 int ans = 0; int cnt = 0; for (int i = 1; i <= m; i++) { // e[i].u <-> e[i].v : e[i].w // 如果会构成环，就不选，否则就选 int faU = findFa(e[i].u); int faV = findFa(e[i].v); if (faU != faV) { fa[faU] = faV; ans += e[i].w; cnt++; } } if (cnt == n - 1) cout << ans << "\n"; else cout << "orz\n"; return 0; }Prim
朴素暴力做法
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; // 无穷大 int n, m; // n个点 m条边 struct Edge { int v, w; }; vector<Edge> e[5005]; // e[i] 储存所有与点i相连的边 int dis[5005]; // 每个点到树的最短距离 int vis[5005]; // 标记给个点是否已经被选择了 int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; e[u].push_back((Edge){v, w}); e[v].push_back((Edge){u, w}); } for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = false; dis[1] = 0; int ans = 0; for (int i = 1; i <= n; i++) // 做n次 { // 找到距离树最近的未被纳入树的点 int now = -1; for (int j = 1; j <= n; j++) // 枚举每个点 if (vis[j] == false && (now == -1 || dis[j] < dis[now]) && dis[j] != INF) now = j; // 纳入这个点 if (now == -1) // 判无解 { cout << "orz\n"; return 0; } ans += dis[now]; vis[now] = true; dis[now] = 0; // 处理now相连的点 for (int i = 0; i < e[now].size(); i++) { int v = e[now][i].v; int w = e[now][i].w; if (vis[v] == true) continue; dis[v] = min(dis[v], w); } } cout << ans << "\n"; return 0; }优先队列优化
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; // 无穷大 int n, m; // n个点 m条边 struct Edge { int v, w; }; vector<Edge> e[5005]; // e[i] 储存所有与点i相连的边 int dis[5005]; // 每个点到树的最短距离 int vis[5005]; // 标记给个点是否已经被选择了 struct Point { int id, dis; }; bool operator<(const Point &x, const Point &y) { return x.dis > y.dis; } priority_queue<Point> q; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; e[u].push_back((Edge){v, w}); e[v].push_back((Edge){u, w}); } for (int i = 1; i <= n; i++) { dis[i] = INF, vis[i] = false; } dis[1] = 0; q.push((Point){1, 0}); int ans = 0; for (int i = 1; i <= n; i++) // 做n次 { // 找到距离树最近的未被纳入树的点 while (!q.empty() && vis[q.top().id]) q.pop(); int now = -1; if (!q.empty()) { now = q.top().id; q.pop(); } // 纳入这个点 if (now == -1) // 判无解 { cout << "orz\n"; return 0; } ans += dis[now]; vis[now] = true; dis[now] = 0; // 处理now相连的点 for (int i = 0; i < e[now].size(); i++) { int v = e[now][i].v; int w = e[now][i].w; if (vis[v] == true) continue; if (w < dis[v]) { dis[v] = w; q.push((Point){v, w}); } } } cout << ans << "\n"; return 0; }
- 1