VMCOMP - Công việc tuyển dụng
Tác giả: skyvn97
Ngôn ngữ: C++
#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;
}