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;
}