题解 P1657 【选书】

cy汀 · 2019-11-07 20:15:48 · 题解

P1657 题解

这道题要求m本书分配给m个人，然后数据范围太水了（n<=20）。所以索性开始暴力dfs。

#include<bits/stdc++.h>
using namespace std;
int flag=0;
bool ans[21]={false};
int x,a1[21],a2[21];//记录喜欢哪几本书 
void dfs(int m)//表示选到第m本书，第m本没选 
{
    if(m>x)//选完了 
    {
        flag++;//方案 
        return;
    }
    for(int i=1;i<=x;i++)//枚举第m个人需要的 
    {
        if(ans[i]==false && (a1[m]==i || a2[m]==i))//如果可以且没被选 
        {
            ans[i]=true;//标记 
            dfs(m+1);
            ans[i]=false;//回溯 
        }
     } 
}
int main()
{
    cin>>x;
    if(x==0)//数据坑的特判 
    {
        cout<<0;
        return 0; 
    }
    for(int i=1;i<=x;i++)
    {
        cin>>a1[i]>>a2[i];
    }
    dfs(1);
    cout<<flag;
    return 0;
}