HDU5627 Clarke and MST {图论}【生成树】（最大生成树，Prim）

题意

    给定$n$个点和$m$条边及其权值，构造一棵生成树，使得生成树的权值按位与（$\&$）值最大。

题解

    直接使用$prim$算法即可，$ans$的初始值赋值为第一条加入的边，用一个$bool$变量来判断。

#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <functional> #include <iostream> #include <map> #include <queue> #include <stack> #include <string> #include <unordered_map> #include <vector> #define lowbit(x) ((x) & -(x)) using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 1e6 + 10, NN = 2e3 + 10, INF = 0x3f3f3f3f, LEN = 20; const ll MOD = 1e9 + 7; const ull seed = 31; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } struct Edge { int next, to, dis; bool friend operator<(const Edge& a, const Edge& b) { return a.dis < b.dis; } } edge[N]; int n, m, num_edge, cnt, ans; int head[N]; bool flag; bool vis[N]; void add_edge(int from, int to, int dis) { edge[num_edge].next = head[from]; edge[num_edge].to = to; edge[num_edge].dis = dis; head[from] = num_edge++; } void init() { flag = false; num_edge = cnt = ans = 0; memset(head, -1, sizeof head); memset(vis, false, sizeof vis); } bool prim() { priority_queue<Edge> q; vis[1] = true; ++cnt; for (int i = head[1]; i != -1; i = edge[i].next) { int v = edge[i].to; if (vis[v]) continue; q.push(edge[i]); } while (!q.empty()) { int point = 0; Edge u = q.top(); point = u.to; if (vis[point]) { q.pop(); continue; } ++cnt; if (!flag) { ans = u.dis; flag = true; } else ans &= u.dis; vis[point] = true; if (cnt == n) break; for (int i = head[point]; i != -1; i = edge[i].next) { int v = edge[i].to; if (vis[v]) continue; q.push(edge[i]); } } if (cnt == n) return true; else return false; } int main() { int T; scanf("%d", &T); while (T--) { init(); scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add_edge(u, v, w); add_edge(v, u, w); } if (prim()) printf("%d\n", ans); else printf("0\n"); } }