VMCOMP - Công việc tuyển dụng

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>

#define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i >= _b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
using namespace std;

int n, m, s;
long long sum[100111];
vector< pair<int,int> > ke[100111];
set< pair<long long,int> > all;
bool used[100111];

int main() {
    while (scanf("%d%d%d", &n, &m, &s) == 3) {
        FOR(i,1,n) {
            ke[i].clear();
            sum[i] = 0;
        }

        while (m--) {
            int u, v, c; scanf("%d%d%d", &u, &v, &c);
            ke[u].push_back(make_pair(v, c));
            ke[v].push_back(make_pair(u, c));
            sum[u] += c;
            sum[v] += c;
        }

        all.clear();
        FOR(i,1,n) all.insert(make_pair(sum[i], i));

        while (!all.empty()) {
            pair<long long,int> cur = *all.begin();
            if (cur.first >= s) break;

            all.erase(all.begin());
            int u = cur.second;
            sum[u] = -1;

            REP(i,ke[u].size()) {
                int v = ke[u][i].first, c = ke[u][i].second;
                if (sum[v] < 0) continue;

                all.erase(make_pair(sum[v], v));

                sum[v] -= c;

                all.insert(make_pair(sum[v], v));
            }
        }

        memset(used, false, sizeof used);
        while (!all.empty()) {
            pair<long long,int> cur = *all.begin(); all.erase(all.begin());
            used[cur.second] = true;
        }
        int res = 0;
        FOR(i,1,n) if (used[i]) ++res;
        if (res == 0) {
            puts("-1");
        }
        else {
            printf("%d\n", res);
            FOR(i,1,n) if (used[i]) printf("%d ", i);
            puts("");
        }
    }
    return 0;
}

Download