自动搬运

查看原文

来自洛谷，原作者为

	xcc **

搬运于2025-08-24 21:27:36，当前版本为作者最后更新于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;
}