博客

题意

给定



n

n






n





个点和



m

m






m





条边及其权值，构造一棵生成树，使得生成树的权值按位与（



&

\&






&





）值最大。

题解

直接使用



p

r

i

m

prim






p


r


i


m





算法即可，



a

n

s

ans






a


n


s





的初始值赋值为第一条加入的边，用一个



b

o

o

l

bool






b


o


o


l





变量来判断。

#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");
    }
}