公司的论坛与网站绑定,南城区做网站,深度网络科技有限公司,网站怎么加友情链接Problem - D - Codeforces 思路#xff1a;这个题就是求环的数量#xff0c;通过数据范围的大小#xff0c;我们可以想到用状压dp来做#xff0c;因为只有19个点#xff0c;我们可以将环的路径进行状态压缩#xff0c;用一个二进制数表示环#xff0c;当某一位为1时表示…Problem - D - Codeforces 思路这个题就是求环的数量通过数据范围的大小我们可以想到用状压dp来做因为只有19个点我们可以将环的路径进行状态压缩用一个二进制数表示环当某一位为1时表示这个点在环上那么我们可以用f[i][j]表示当前的路径状态为i当前所在的点为j的情况为了让环不重复统计那么我们可以将路径中最小的点作为起点可以保证不重复那么我们只需要将状态从小到大枚举这样一定会枚举到所有的情况因为i一定是变大的不会变小然后再枚举现在再哪个位置了再枚举接下来要走到哪个点那么如果当前的位置或者要到的位置比起点的编号小了那么就跳过并且如果从当前位置不能够走到下一个位置也跳过并且我们再更新i的过程中要保证路径i没有环因为如果存在环会重复统计。
// Problem: D. A Simple Task
// Contest: Codeforces - Codeforces Beta Round 11
// URL: https://codeforces.com/contest/11/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms#includebits/stdc.h
#includesstream
#includecassert
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pairint,int PII;
const double eps1e-7;
const int N5e57 ,M5e57, INF0x3f3f3f3f,mod1e97,mod1998244353;
const long long int llINF0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x0,f1;char cgetchar();while(c0||c9) {if(c-) f-1;cgetchar();}
while(c0c9) {x(ll)x*10c-0;cgetchar();} return x*f;}
inline void write(ll x) {if(x 0) {putchar(-); x -x;}if(x 10) write(x / 10);putchar(x % 10 0);}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen(in_put.txt,r,stdin);freopen(my_out_put.txt,w,stdout);}
bool cmp0(int a,int b) {return ab;}
templatetypename T T gcd(T a,T b) {return b0?a:gcd(b,a%b);}
templatetypename T T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf(\n----------------------------------\n);}int T,hackT;
int n,m,k;
bool st[30][30];
ll f[120][20];int lowbit(int x) {return x-x;
}void solve() {nread(),mread();for(int i1;im;i) {int aread(),bread();st[a-1][b-1]st[b-1][a-1]true;} for(int i0;in;i) f[1i][i]1;ll res0;for(int i0;i(1n);i) {int startlowbit(i);for(int j0;jn;j) {if((1j)start) continue;for(int k0;kn;k) {if((1k)start) continue;if(!st[j][k]) continue;if(start(1k)) {resf[i][j];}else if(!((ik)1)){f[i|(1k)][k]f[i][j];}}}}res(res-m)/2;printf(%lld\n,res);
}int main() {// init();// stin();// ios::sync_with_stdio(false); // scanf(%d,T);T1; while(T--) hackT,solve();return 0;
}
