题意: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;
}