题意 : 给出两幅顶点数一样的图 G1、G2 ，现在要求在 G2 中选出一些边集、使之构成一幅新的图 G ，要求 G 要与 G1 同构，现在要你统计合法的 G 有多少种
分析 :
图的同构是离散数学里面图论的一个概念、具体的可以看 这里
判断两幅图是否是同构的至今貌似还是 NP 问题
由于顶点数最多只有 8、同时意味着边最多只有 28
那么可以由此想到 O(n!) 枚举所有的顶点的双射 (实际就是枚举全排列)
考察每个双射下两图是否能够构成同构关系
判断是否构成双射只要考察其邻接矩阵是否能一样即可
这就意味着去选出 G2 这副图中的某些边集
使得当前枚举到的双射能够使得 G1 和 G2 同构
由于边不多、所以可以状态压缩这些边集
存到一个 set 中进行去重、最后 set 的大小即为答案
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
还有另外一种做法就是
枚举双射计算出 G1 和 G2 同构方案数
然后再计算出 G1 和 G1 自己的自同构方案数
最后答案就是 ( G1 和 G2 同构方案数 ) / ( G1 和 G1 自己的自同构方案数 )
说实话、这个东西、我并不是很理解...........
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define scl(i) scanf("%lld", &i) #define scll(i, j) scanf("%lld %lld", &i, &j) #define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k) #define scllll(i, j, k, l) scanf("%lld %lld %lld %lld", &i, &j, &k, &l) #define scs(i) scanf("%s", i) #define sci(i) scanf("%d", &i) #define scd(i) scanf("%lf", &i) #define scIl(i) scanf("%I64d", &i) #define scii(i, j) scanf("%d %d", &i, &j) #define scdd(i, j) scanf("%lf %lf", &i, &j) #define scIll(i, j) scanf("%I64d %I64d", &i, &j) #define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k) #define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k) #define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k) #define sciiii(i, j, k, l) scanf("%d %d %d %d", &i, &j, &k, &l) #define scdddd(i, j, k, l) scanf("%lf %lf %lf %lf", &i, &j, &k, &l) #define scIllll(i, j, k, l) scanf("%I64d %I64d %I64d %I64d", &i, &j, &k, &l) #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define lowbit(i) (i & (-i)) #define mem(i, j) memset(i, j, sizeof(i)) #define fir first #define sec second #define VI vector<int> #define ins(i) insert(i) #define pb(i) push_back(i) #define pii pair<int, int> #define mk(i, j) make_pair(i, j) #define all(i) i.begin(), i.end() #define pll pair<long long, long long> #define _TIME 0 #define _INPUT 0 #define _OUTPUT 0 clock_t START, END; void __stTIME(); void __enTIME(); void __IOPUT(); using namespace std; const int maxn = 8 + 5; int G1[maxn][maxn]; int G2[maxn][maxn]; map<pii, int> mp; set<LL> ans; int main(void){__stTIME();__IOPUT(); int n, m1, m2; while(~sciii(n, m1, m2)){ mem(G1, 0); mem(G2, 0); ans.clear(); mp.clear(); for(int i=0; i<m1; i++){ int u, v; scii(u, v); G1[u][v] = G1[v][u] = 1; } for(int i=0; i<m2; i++){ int u, v; scii(u, v); if(u < v) swap(u, v); mp[mk(u,v)] = i; G2[u][v] = G2[v][u] = 1; } int idx[maxn]; for(int i=1; i<=n; i++) idx[i] = i; do{ LL state = 0; bool ok = true; for(int i=1; i<=n; i++){///判断是否能构成同构 for(int j=1; j<=n; j++){ if(G1[i][j] && !G2[idx[i]][idx[j]]){///只考虑G1有边关联的两个顶点的情况 ok = false; break; }else{ if(G1[i][j]){ int u = idx[i]; int v = idx[j]; if(u < v) swap(u, v); state |= (1LL<<mp[mk(u,v)]);///状态压缩 } } } if(!ok) break; } if(!ok) continue; ans.ins(state); }while(next_permutation(idx+1, idx+1+n)); printf("%d ", (int)ans.size()); } __enTIME();return 0;} void __stTIME() { #if _TIME START = clock(); #endif } void __enTIME() { #if _TIME END = clock(); cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl; #endif } void __IOPUT() { #if _INPUT freopen("in.txt", "r", stdin); #endif #if _OUTPUT freopen("out.txt", "w", stdout); #endif }