选择k个节点

题目描述

（假设题目为：从n个节点的无向图中选择k个节点，使得它们的权值之和最大，且任意两个节点不相邻）

输入输出格式

输入

第一行包含两个整数n, m（节点数，边数） 接下来m行，每行两个整数u, v表示一条无向边 接下来一行包含n个整数w_1, w_2, ..., w_n（每个节点的权值） 最后一行包含一个整数k（要选择的节点数）

输出

一行k个整数，为选择的节点编号，按升序排列

样例输入输出

样例输入1

7 3 1 2 2 3 3 4 1 2 3 4 5 6 7 3

样例输出1

3 5 7

解题思路

1. 将节点按权值从大到小排序
2. 贪心选择节点，确保选择的节点之间没有边相连
3. 若选择的节点数不足k，继续选择下一个权值最大的节点

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<unordered_set<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].insert(v);
        adj[v].insert(u);
    }
    
    vector<int> w(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }
    
    int k;
    cin >> k;
    
    vector<pair<int, int>> nodes;
    for (int i = 1; i <= n; ++i) {
        nodes.emplace_back(w[i], i);
    }
    
    sort(nodes.rbegin(), nodes.rend());
    
    vector<bool> selected(n + 1, false);
    vector<int> res;
    
    for (auto [val, u] : nodes) {
        if (res.size() >= k) break;
        bool ok = true;
        for (int v : adj[u]) {
            if (selected[v]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            selected[u] = true;
            res.push_back(u);
        }
    }
    
    sort(res.begin(), res.end());
    for (int i = 0; i < res.size(); ++i) {
        cout << res[i] << (i == res.size() - 1 ? "\n" : " ");
    }
    
    return 0;
}

样例输入输出 1 解释 选择 3, 5, 7 三个节点。 对于全部的测试点，保证 $1 \leq n \leq 5 \times 10^5$，$1 \leq m \leq 2 \times 10^6$，$0 \leq w_i \leq 10^3$，$0 \leq k \leq n$。