题解 P1657 【选书】

_xcc_ · 2016-08-19 09:47:13 · 题解

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

#include<iostream>
using namespace std;
int book[50],s,x;
bool flag[50],like[50][50];              //like[i][j]表示第i个人喜欢第j本书。
void so(int i)                           //dfs产生全排列
{
    int j;
    for(j=1;j<=x;j++)
    {
        if(flag[j]&&like[i][j]){         //此书未选且第i个人喜欢这本书
            flag[j]=0;
            book[i]=j;
            if(i==x) s++;
                else so(i+1);            //继续列举第i+1个人的书
            flag[j]=1;                   //还原与回溯
            book[i]=0;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);         //加快cin、cout（装逼专用）
    cin>>x;
    int i,t1,t2;
    for(i=1;i<=x;i++)                    //读入喜欢列表
    {
        cin>>t1>>t2;
        like[i][t1]=true;
        like[i][t2]=true;
    }
    for(i=1;i<=x;i++)
    {
        flag[i]=true;                   //标记数组初始化
    }
    so(1);
    cout<<s;                            //输出总方案数
    return 0;
}