题目链接：传送门
题意：
n个人给定m个关系，每个关系为x,y表示x,y是朋友，但是可能是online friends,也可能是offline friends.
要求每个人的online 和offline 朋友的数量是一样多的，问有多少种可能。
分析：
n<=8， 因此m<=28.由题意可以知道，每个人的关系数必须为偶数，，然后我们可以枚举一个关系的状态，通过
每个人的online,与offline关系数量小于等于1/2关系总数来剪枝。
代码如下：
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>using namespace std;const int maxn = 10;int du[maxn];int n,m;int on[maxn],off[maxn];int edge[maxn*maxn][2];int ans;void dfs(int id){if(id==m){ans++;return;}on[edge[id][0]]++;on[edge[id][1]]++;if(on[edge[id][0]]*2<=du[edge[id][0]]&&on[edge[id][1]]*2<=du[edge[id][1]])dfs(id+1);on[edge[id][0]]–;on[edge[id][1]]–;off[edge[id][0]]++;off[edge[id][1]]++;if(off[edge[id][0]]*2<=du[edge[id][0]]&&off[edge[id][1]]*2<=du[edge[id][1]])dfs(id+1);off[edge[id][0]]–;off[edge[id][1]]–;}int main(){int t;scanf("%d",&t);while(t–){scanf("%d%d",&n,&m);ans=0;memset(du,0,sizeof(du));for(int i=0;i<m;i++){scanf("%d%d",&edge[i][0],&edge[i][1]);du[edge[i][0]]++;du[edge[i][1]]++;}bool tag = 0;if(m&1) tag=1;for(int i=1;i<=n;i++) if(du[i]&1) tag=1;if(tag){puts("0");continue;}memset(on,0,sizeof(on));memset(off,0,sizeof(off));dfs(0);printf("%d\n",ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
往往为了自己的不能失败，而处心积虑前怕狼后怕虎，
