VMCOMP - Công việc tuyển dụng
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
#define ii pair<int, int>
#define li pair<long long, int>
#define X first
#define Y second
const int N = 100050;
using namespace std;
vector<ii> a[N];
vector<int> res;
int n, m, s;
bool out[N];
long long f[N];
void Enter() {
//freopen("VMCOMP.in", "r", stdin);
scanf("%d %d %d\n", &n, &m, &s);
int u, v, c;
while (m--) {
scanf("%d %d %d\n", &u, &v, &c);
a[u].push_back(ii(v, c));
a[v].push_back(ii(u, c));
f[u] += c; f[v] += c;
}
}
void Build() {
//assume that all vertexes are included in the optimal set
//eliminate vertexes which are not satisfied
priority_queue<li, vector<li>, greater<li> > Q;
int i, u, v, fu, uv;
for(i=1; i<=n; i++) Q.push(ii(f[i], i));
while (Q.size()) {
u = Q.top().Y; fu = Q.top().X;
Q.pop();
if (out[u] || ((!out[u]) && fu != f[u])) continue;
if (fu >= s) break;
out[u] = true;
for(i=0; i<a[u].size(); i++) {
v = a[u][i].X; uv = a[u][i].Y;
f[v] -= uv;
if (out[v]) continue;
Q.push(ii(f[v], v));
}
}
for(i=1; i<=n; i++)
if (!out[i]) res.push_back(i);
if (res.size() == 0) printf("-1"); else {
printf("%d\n", res.size());
for(i=0; i<res.size(); i++) printf("%d ", res[i]);
}
}
int main()
{
Enter();
Build();
return 0;
}