竞赛讨论区 > 牛客网ACM多校(第一场)D Two Graphs[模拟]
头像
whshowell
编辑于 2018-07-29 11:06
+ 关注

牛客网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;
}
最后附上我的博客链接希望大家不要吐槽我菜!!!

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐