Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int n, S;
long long sum[100100];
vector <int> a[100100], c[100100];

int main()
{
    int m, x, y, z;
    cin >> n >> m >> S;
    while (m--)
    {
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(y); c[x].push_back(z);
        a[y].push_back(x); c[y].push_back(z);
        sum[x] += z;
        sum[y] += z;
    }

    queue <int> q;
    for (int i = 1; i <= n; i++)
        if (sum[i] < S) q.push(i);

    int ans = n;
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        ans--;
        for (int i = 0; i < int(a[x].size()); i++)
        {
            int y = a[x][i];
            if (sum[y] >= S)
            {
                sum[y] -= c[x][i];
                if (sum[y] < S) q.push(y);
            }
        }
    }

    if (!ans) puts("-1");
    else 
    {
        cout << ans << endl;
        for (int i = 1; i <= n; i++)
            if (sum[i] >= S) printf("%d ", i);
    }
}

Code mẫu của happyboy99x

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

Code mẫu của ladpro98

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

Code mẫu của RR

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

Code mẫu của skyvn97

#include<cstdio>
#include<set>
#include<vector>
#define MAX   100100
#define v   first
#define p   second
using namespace std;
typedef long long ll;
typedef pair<ll,int> ii;
typedef set<ii> sii;
vector<ii> g[MAX];
sii st;
ll s[MAX];
int m,n;
bool r[MAX];
ll q;
void init(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    scanf("%lld",&q);
    int i,u,v;
    ll w;
    for (i=1;i<=n;i=i+1) {
        s[i]=0;
        g[i].clear();
        r[i]=true;
    }
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&u); 
        scanf("%d",&v);
        scanf("%lld",&w);
        g[u].push_back(ii(w,v));
        g[v].push_back(ii(w,u));
        s[u]+=w;
        s[v]+=w;
    }
    st.clear();
    for (i=1;i<=n;i=i+1) st.insert(ii(s[i],i));
}
void process(void) {
    int i,c,k,u;    
    while (true) {
        k=(int)st.size();       
        if (k<2) {
            printf("-1");
            return;
        }
        if ((*st.begin()).v>=q) {       
            printf("%d\n",k);           
            c=0;
            for (i=1;i<=n;i=i+1)
                if (r[i]) {
                    printf("%d",i);
                    c++;
                    if (c<k) printf(" ");
                }
            return;
        }       
        u=(*st.begin()).p;      
        r[u]=false;
        st.erase(st.begin());
        for (i=0;i<g[u].size();i=i+1) 
            if (r[g[u][i].p]) {             
                st.erase(st.find(ii(s[g[u][i].p],g[u][i].p)));              
                s[g[u][i].p]-=g[u][i].v;                
                st.insert(ii(s[g[u][i].p],g[u][i].p));                          
            }                   
    }
}
int main(void) {
    init();
    process();
    return 0;
}