洛谷题解 P1657 【选书】

  • A+
所属分类:代码笔记 信息技术

主要思路就是产生书的全排列(用dfs,可优化),排除与喜欢列表不符合的方案。

  1. #include<iostream>  
  2. using namespace std;  
  3. int book[50],s,x;  
  4. bool flag[50],like[50][50];              //like[i][j]表示第i个人喜欢第j本书。  
  5. void so(int i)                           //dfs产生全排列  
  6. {  
  7.     int j;  
  8.     for(j=1;j<=x;j++)  
  9.     {  
  10.         if(flag[j]&&like[i][j]){         //此书未选且第i个人喜欢这本书  
  11.             flag[j]=0;  
  12.             book[i]=j;  
  13.             if(i==x) s++;  
  14.                 else so(i+1);            //继续列举第i+1个人的书  
  15.             flag[j]=1;                   //还原与回溯  
  16.             book[i]=0;  
  17.         }  
  18.     }  
  19. }  
  20. int main()  
  21. {  
  22.     ios::sync_with_stdio(false);         //加快cin、cout(装逼专用)  
  23.     cin>>x;  
  24.     int i,t1,t2;  
  25.     for(i=1;i<=x;i++)                    //读入喜欢列表  
  26.     {  
  27.         cin>>t1>>t2;  
  28.         like[i][t1]=true;  
  29.         like[i][t2]=true;  
  30.     }  
  31.     for(i=1;i<=x;i++)  
  32.     {  
  33.         flag[i]=true;                   //标记数组初始化  
  34.     }  
  35.     so(1);  
  36.     cout<<s;                            //输出总方案数  
  37.     return 0;  
  38. }  
xcc

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: