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

Download