题意 : 给出两幅顶点数一样的图 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
      
       #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
       
        #define ins(i) insert(i)#define pb(i) push_back(i)#define pii pair
        
         #define mk(i, j) make_pair(i, j)#define all(i) i.begin(), i.end()#define pll pair
         
          #define _TIME 0#define _INPUT 0#define _OUTPUT 0clock_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
          
            mp;set
           
             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