PAT (Advanced Level) Practice - 1053 Path of Equal Weight（30 分）

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintN=109;
structnode{
intid,val;
}nds[N];
structsort_vec{
vector<int>rsv;
}sv[N];
vector<node>v[N];
intn,k,len;
inta[N];
voiddfs(intrt, intsum, intl)
{
if(sum==k&&v[rt].size()==0)
    {
for(inti=0;i<l;i++) sv[len].rsv.push_back(a[i]);
len++;
return;
    }
for(inti=0;i<v[rt].size();i++)
    {
intw=v[rt][i].val;
if(sum+w>k) continue;
a[l]=w;
dfs(v[rt][i].id,sum+w,l+1);
    }
}
intcmp(sort_vecsv1,sort_vecsv2)
{
returnsv1.rsv>sv2.rsv;
}
intmain()
{
intm,cnt,id,cid,rt=0;
scanf("%d%d%d",&n,&m,&k);
for(inti=0;i<n;i++) scanf("%d",&nds[i].val);
for(inti=0;i<m;i++)
    {
scanf("%d%d",&id,&cnt);
while(cnt--)
        {
scanf("%d",&cid);
nds[cid].id=cid;
v[id].push_back(nds[cid]);
        }
    }
a[0]=nds[rt].val;
dfs(rt,a[0],1);
sort(sv,sv+len,cmp);
for(inti=0;i<len;i++)
for(intj=0;j<sv[i].rsv.size();j++)
printf("%d%c",sv[i].rsv[j],j==sv[i].rsv.size()-1?'\n':' ');
return0;
}