牛客网ACM多校(第一场)D Two Graphs[模拟]
题目:要求计算与A同构的B的子图的个数;
思路:将A图全排列映射到B图中,判断是否同构,每个B与A同构的子图,都计算了A的“自同构”次,去重得到答案;
解释一下为什么会多算看下面这张图:
考虑G1边互换两个节点,也可以构成同构,在G2中每一种方案也可以通过互换顺序,得到另一种同构,但其本质是相同的,所以找出G1中自同构的数量,每个满足题意的方案被计算了“自同构”次,除去就是答案;
代码:
#include<bits/stdc++.h> #define ll long long using namespace std; int m1, m2, n; struct Edge{int a, b;}; using Graph = vector<Edge>; Graph read(int m) { Graph ans; for(int i = 0, a, b; i < m; i++) { scanf("%d%d", &a, &b); a--; b--; ans.push_back(Edge{a, b}); } return ans; } int count(int n, const Graph &a, const Graph &b) { vector< vector<bool> > target(n, vector<bool>(n, false)); for(auto&& e : b) target[e.a][e.b] = target[e.b][e.a] = true; vector<int> phi(n); iota(phi.begin(), phi.end(), 0); int ans = 0; do{ bool k = true; for(auto&& e : a) k &= target[phi[e.a]][phi[e.b]]; ans += k; if(k) { for(auto&& e : a) { printf("%d %d\n", phi[e.a], phi[e.b]); } printf("\n"); } } while(next_permutation(phi.begin(), phi.end())); return ans; } int main() { freopen("in.txt", "r", stdin); while(~scanf("%d%d%d", &n, &m1, &m2)) { auto A = read(m1); auto B = read(m2); int isab = count(n, A, B); int isaa = count(n, A, A); //printf("%d %d\n", isab, isaa); printf("%d\n", isab/isaa); } return 0; }
最后附上我的博客链接希望大家不要吐槽我菜!!!