本文主要是介绍浙大PAT 1053题 1053. Path of Equal Weight，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*
关键是要想到：不要在过程中考虑排序，好的做法是
先将每次的结果保存在字符串中，最后排序输出。
*/
#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;
}
这篇关于浙大PAT 1053题 1053. Path of Equal Weight的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
