PTA 最小生成树的唯一性——次小生成树

PTA 最小生成树的唯一性——次小生成树

先dfs一遍求一下连通块的个数，连通块为1的情况下求出最小生成树和次小生成树，判断两者是否相等

#include #include #include #include #include using namespace std;const int maxn = 510;const int INF = 0x3f3f3f3f;int n, m;vector G[maxn];struct Edge { bool flag; int u, v, cost; bool operator < (const Edge &e) const { return cost < e.cost; }}edge[maxn*maxn];bool vis[maxn];void dfs(int u) { for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (vis[v]) continue; vis[v] = true; dfs(v); }}vector p[maxn];int dis[maxn][maxn];int fa[maxn];int query(int x) { return fa[x] == x ? x : fa[x] = query(fa[x]); }void mst() { for (int i = 1; i <= n; i++) p[i].push_back(i); for (int i = 1; i <= n; i++) fa[i] = i; sort(edge, edge+m); int cnt = 0; for (int i = 0; i < m && cnt < n-1; i++) { int u = edge[i].u, v = edge[i].v, cost = edge[i].cost; u = query(u), v = query(v); if (u == v) continue; for (int j = 0; j < p[u].size(); j++) { for (int k = 0; k < p[v].size(); k++) { int x = p[u][j], y = p[v][k]; dis[x][y] = dis[y][x] = cost; } } for (int k = 0; k < p[v].size(); k++) p[u].push_back(p[v][k]); fa[v] = u; edge[i].flag = true; cnt++; }}int main() { cin >> n >> m; int u, v, cost; for (int i = 0; i < m; i++) { cin >> u >> v >> cost; G[u].push_back(v); G[v].push_back(u); edge[i].u = u, edge[i].v = v, edge[i].cost = cost, edge[i].flag = false; } int cnt = 0; memset(vis, false, sizeof(vis)); for (int i = 1; i <= n; i++) { if (!vis[i]) { vis[i] = true; cnt++; dfs(i); } } if (cnt > 1) { cout << "No MST" << endl << cnt << endl; } else { mst(); int sum = 0, ans = INF; for (int i = 0; i < m; i++) if (edge[i].flag) sum += edge[i].cost; for (int i = 0; i < m; i++) { if (edge[i].flag) continue; ans = min(ans, sum-dis[edge[i].u][edge[i].v]+edge[i].cost); } cout << sum << endl; if (ans != sum) cout << "Yes" << endl; else cout << "No" << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。