题目链接
题意：t 组测试数据，每组测试数据有 n个人，m条关系
每条关系可以是 “线上关系” 或者 “线下关系”， 要求每个人的线上关系（条数） == 线下关系（条数）
问共有几种分配方法
思路：
①因为要使每个人的线上关系的总数== 线下关系 的总数，那么总关系数一定是偶数所以当m为奇数时，方法数肯定为0；
②因为每条边只有两种状态，online 或 offline，所以可以用壮压来做，1表示online, 0表示offline;
③m最大有(8*(8-1))/2 = 28条，，1<<28 很大，要TLE，所以用中途相遇法来做
④将每种状态每个点的 online 和offline个数到 p[N] 里（p[N]用pair定义）然后前半部分倒置存入map数组就可以了
代码如下：
#include<cstdio>#include<cstring>#include<cmath>#include<string>#include<iostream>#include<algorithm>#include<map>using namespace std;typedef long long ll;typedef pair<ll, ll>pii; const int N = 1e5+10;const int INF = 1e9+7;int n, m;int x[100], y[100];int s[100], e[100];int on[10], off[10];map<pii, int>mp;pii p[1 << 14];void work(){for(int i = 0; i < (1 << (m/2)); i++){memset(on, 0,sizeof(on));memset(off, 0, sizeof(off));for(int j = 0; j < (m/2); j++){if(i & (1 << j)){on[s[j]]++, on[e[j]]++;}else{off[s[j]]++, off[e[j]]++;}}for(int k = 0; k < n; k++){int cnt = min(on[k], off[k]);on[k] -= cnt, off[k] -= cnt;}p[i] = {0,0};for(int k = 0; k < n; k++) {p[i].first = p[i].first * 100 + on[k];p[i].second = p[i].second * 100 + off[k];}}}int main(){int t;scanf("%d", &t);while(t–){scanf("%d%d", &n, &m);for(int i = 0; i < m; i++){scanf("%d%d", &x[i], &y[i]);x[i]–, y[i]–;}if(m % 2) {printf("0\n"); continue;}for(int i = 0; i < (m/2); i++){s[i] = x[i], e[i] = y[i];}work();mp.clear();for(int i = 0; i < (1 << (m/2)); i++){mp[{p[i].second, p[i].first}]++;}for(int i = m/2; i < m; i++){s[i-m/2] = x[i], e[i-m/2] = y[i];}work();ll ans = 0;for(int i = 0; i < (1 << (m/2)); i++){if(mp.count(p[i])){ans += mp[p[i]];}}printf("%I64d\n", ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
才会看到属于自己的那一片晴朗的天空。
