题意是有n个人，m对朋友关系，朋友可以使在线朋友和离线朋友，对于单个人，他的在线朋友和离线朋友数必须一致，请问有几种方案。 题目中n并不大，不超过8，那么暴力一点，用搜索，穷尽所有方案并判断是否可行，求出可行方案数。 为了使搜索更加高效，我们先进行状态压缩，bin(x0,x1,x2…xn)表示一个人的朋友情况，xi位为1表示与i是在线朋友，转化成十进制保存在sta数组。先预处理出，在X个人中选出Y个人的方案，保存在P[X][Y]中。计算出每个人有多少个朋友，保存在cnt数组。 从第一个人开始深搜，枚举P[n][cnt[1]/2]的所有方案，并根据朋友关系改变相应朋友的sta值。第二个人在第一个的基础上枚举P[n-1][cnt[2]/2-has]，has表示已经拥有的在线朋友数，同理，根据方案改变后面的人的sta值…记得回溯时将后面的人的sta值改成原来的值。
#include<map>#include<cmath>#include<ctime>#include<cstdio>#include<vector>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#define LL long longusing namespace std;const int maxn=1005;const LL Inf=1e18;vector<int> Next[10];vector<int> P[10][10];int M[10], cnt[10], sta[10];;int n, m;int ans;int bitcount(int x){ int ret=0; while(x){ if(x&1) ret++; x>>=1; } return ret;}void PRe(){ for(int i=1;i<=8;i++) for(int j=0;j<(1<<i);j++){ int bits=bitcount(j); P[i][bits].push_back(j); }}void dfs(int u){ int has=bitcount(sta[u]); if(2*has>cnt[u]) return; if(n-u<cnt[u]/2-has) return; if(u==n){ ans++; return; } int left=n-u, need=cnt[u]/2-has; for(int i=0;i<P[left][need].size();i++){ int x=P[left][need][i]; if(((x<<u)|M[u])!=M[u]) continue; for(int j=0;j<left;j++) if(x&(1<<j)) sta[u+j+1]|=(1<<(u-1)); dfs(u+1); for(int j=0;j<left;j++) if(x&(1<<j)) sta[u+j+1]^=(1<<(u-1)); }}void solve(){ for(int i=1;i<=n;i++) if(cnt[i]%2){ puts("0"); return; } for(int i=1;i<=n;i++){ M[i]=0; for(int j=0;j<Next[i].size();j++){ M[i]|=(1<<(Next[i][j]-1)); } } ans=0; memset(sta,0,sizeof(sta)); dfs(1); printf("%d/n",ans);}int main(){// freopen("matrix.in","r",stdin);//从in.txt中读取数据// freopen("matrix.out","w",stdout);//输出到out.txt文件 int T; int u, v; pre(); scanf("%d",&T); while(T--){ scanf("%d%d",&n, &m); memset(cnt,0,sizeof(cnt)); for(int i=0;i<=n;i++) Next[i].clear(); for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); cnt[u]++, cnt[v]++; Next[u].push_back(v); Next[v].push_back(u); } solve(); } return 0;}新闻热点
疑难解答
