VMCOMP - Công việc tuyển dụng
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
#define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i)
typedef long long Long;
const int N = 100000;
bool deleted[N];
int n, m, mins, choose[N];
Long eff[N];
vector<vector<pair<int, int> > > g;
set<pair<Long, int> > s;
void enter() {
scanf("%d%d%d", &n, &m, &mins);
g.resize(n);
for(int i = 0; i < m; ++i) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
--u; --v;
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
eff[u] += w; eff[v] += w;
}
}
void solve() {
for(int i = 0; i < n; ++i)
s.insert(make_pair(eff[i], i));
while(!s.empty() && s.begin()->first < mins) {
int u = s.begin()->second;
s.erase(s.begin());
deleted[u] = true;
TR(g[u], it) {
int v = it->first, w = it->second;
if(!deleted[v]) {
s.erase(s.find(make_pair(eff[v], v)));
eff[v] -= w;
s.insert(make_pair(eff[v], v));
}
}
}
}
void print() {
if(s.empty()) printf("-1\n");
else {
int res = 0;
TR(s, it) choose[res++] = it->second;
sort(choose, choose+res);
printf("%d\n", res);
for(int i = 0; i < res; ++i) {
if(i != 0) printf(" ");
printf("%d", choose[i] + 1);
}
printf("\n");
}
}
int main() {
enter();
solve();
print();
return 0;
}