【1053】Path of Equal Weight (30 分)

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      const int MAXN=110;
     
    
   

    

     

    
    

     

      struct node{
     
    
   

    

     

    
    

     
	int weight;  //数据域
     
    
   

    

     

    
    

     

      	vector<int> child; //指针域
     
    
   

    

     

    
    

     

      }Node[MAXN];  //结点数组
     
    
   

    

     

    
    

     

      bool cmp(int a,int b){
     
    
   

    

     

    
    

     
	return Node[a].weight>Node[b].weight; //按结点数据域从大到小排序
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int n,m,S; //结点数 边数 给定的和
     
    
   

    

     

    
    

     

      int path[MAXN];//记录路径
     
    
   

    

     

    
    

     

      //当前访问结点为index，numNode为当前路径path上的结点个数
     
    
   

    

     

    
    

     

      //sum为当前的结点点权和
     
    
   

    

     

    
    

     

      void DFS(int index,int numNode ,int sum){ 
     
    
   

    

     

    
    

     
	if(sum>S)  return ;//当前和sum超过S，直接返回
     
    
   

    

     

    
    

     
	if(sum==S) { //如果当前和sum等于S
     
    
   

    

     

    
    

     
		if(Node[index].child.size() !=0) return;//还没有到叶子结点，直接返回
     
    
   

    

     

    
    

     
		//到达叶子结点，此时path[]存放了一条完整的路径，输出它
     
    
   

    

     

    
    

     
		for(int i=0;i<numNode;i++){
     
    
   

    

     

    
    

     
			printf("%d",Node[path[i]].weight);
     
    
   

    

     

    
    

     
			if(i<numNode-1) printf(" ");
     
    
   

    

     

    
    

     
			else printf("\n");
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		return ;// 返回
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for(int i=0;i<Node[index].child.size() ;i++){ //枚举所有子结点
     
    
   

    

     

    
    

     
		int child=Node[index].child[i]; //结点index的第i的子结点编号
     
    
   

    

     

    
    

     

      		path[numNode]=child;//将结点child加到路径path末尾
     
    
   

    

     

    
    

     
		DFS(child,numNode+1,sum+Node[child].weight); //递归进入下一层
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
   
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	scanf("%d%d%d",&n,&m,&S);
     
    
   

    

     

    
    

     
	for(int i=0;i<n;i++){
     
    
   

    

     

    
    

     
		scanf("%d",&Node[i].weight);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int id,k,child;
     
    
   

    

     

    
    

     
	for(int i=0;i<m;i++){
     
    
   

    

     

    
    

     
		scanf("%d%d",&id,&k); //结点编号及孩子
     
    
   

    

     

    
    

     
		for(int j=0;j<k;j++){
     
    
   

    

     

    
    

     
			scanf("%d",&child);
     
    
   

    

     

    
    

     

      			Node[id].child.push_back(child); //child为结点id的孩子
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		sort(Node[id].child.begin() , Node[id].child.end(),cmp); //排序
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	path[0]=0; //路径的第一个结点设置为0号结点
     
    
   

    

     

    
    

     
	DFS(0,1,Node[0].weight); //DFS求解
     
    
   

    

     

    
    

     
	system("pause"); 
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/99834849