/* 关键是要想到:不要在过程中考虑排序,好的做法是 先将每次的结果保存在字符串中,最后排序输出。 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define maxn 108 int wgt[maxn],map[maxn][maxn],vst[maxn],res[maxn]; char ans[maxn][2*maxn]; int n,m,s,cnt; void dfs(int from,int sum,int step){ int i,j; if(sum>s) return; if(sum==s){ for(i=0;i<n;i++){ if(map[from][i]==1) return; } for(i=0;i<=step;i++){ ans[cnt][i]=res[i]; } ans[cnt][i]='\0'; cnt++; return; } for(i=0;i<n;i++){ if(vst[i]==0&&map[from][i]==1){ vst[i]=1; res[step+1]=wgt[i]; dfs(i,sum+wgt[i],step+1); vst[i]=0; } } return; } int cmp(const void* tmpa,const void* tmpb){ char* a=(char*)tmpa; char* b=(char*)tmpb; return strcmp(b,a); } int main(){ int i,j,k; int f,t; scanf("%d %d %d",&n,&m,&s); for(i=0;i<n;i++){ scanf("%d",&wgt[i]); } for(i=0;i<n;i++){ vst[i]=0; for(j=0;j<n;j++){ map[i][j]=0; } } for(i=0;i<m;i++){ scanf("%d %d",&f,&k); for(j=0;j<k;j++){ scanf("%d",&t); map[f][t]=1; } } cnt=0; vst[0]=1; res[0]=wgt[0]; dfs(0,wgt[0],0); qsort(ans,cnt,sizeof(ans[0]),cmp); for(i=0;i<cnt;i++) { for(j=0;j<strlen(ans[i])-1;j++) printf("%d ",ans[i][j]); printf("%d\n",ans[i][j]); } return 0; }