luoguP1657 选书

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
using namespace std;
int n,ans;
bool visb[30],viss[30];
//visb:一本书(visb[x])是否已经被选择
//viss:一个学生(viss[x])是否已经选择一本书
vector<pair<int,int> > vec;
void dfs(int x){//当前枚举的是第x本书
if(x==n+1){//边界条件
ans++;
return;
}
for(int i=0;i<n;i++){
if((vec[i].first==x||vec[i].second==x) && !visb[x] && !viss[i]){//如果一个学生想要这本书且这本书没有被选中且这个学生没有选任何一本书
visb[x] = true;//这本书已被选择
viss[i] = true;//学生已选择一本书
dfs(x+1);//枚举下一本书
viss[i] = false;
visb[x] = false;
}
}
}
int main() {
cin >> n;
for(int i=0;i<n;i++){
int x,y;
cin >> x >> y;
vec.push_back({x,y});
}
if(n!=0)
dfs(1);
cout << ans << endl;
return 0;
}

luoguP1657 选书
https://www.d0j1a1701.cc/p/f2947e1e/
作者
d0j1a_1701
发布于
2020年8月12日
许可协议
CC-BY-SA