2018牛客网暑期多校 D-Two Graphs 【构造+全排列】

发表于 | 分类于

题目链接：戳这里

题意：给出G1，G2两个图判断G2中有多少个子图与G1同构。

解题思路：这题的难点在于构造。我们可以设一个mp数组作为G1的映射，然后全排列mp数组，判断G2中有多少个子图与G1同构。

例如：

G1　　　mp[1]=1 mp[2]=2 mp[3]=3　　　mp[1]=1 mp[2]=3 mp[3]=2　　　…

1 2　　　mp[1] mp[2]　　　　　　　　　　mp[1] mp[3]

1 3　　　mp[1] mp[3]　　　　　　　　　　mp[1] mp[2]

首先我们映射mp[i] = i, 然后对mp[]全排列，这样就相当于画出G1的所有构造可能，看G2中有没有完全满足G1中所有边关系的图,如果有，就说此时的映射mp是G2的子图，cnt2++。
因为在全排列mp[]的过程中，也会遇到mp[]与G1同构的情况，所以也要记录cnt1的个数，最后的答案就是cnt2/cnt1。

附ac代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 211;
const int maxx = 11;
bool nu1[maxx][maxx];
bool nu2[maxx][maxx];
int v[maxn];
int u[maxn];
int mp[maxx];
int main()
{
    int n, m1, m2;
    int x, y;
   // int ans = 0;
    while(~scanf("%d %d %d", &n, &m1, &m2))
    {
        memset(nu1, 0, sizeof(nu1));
        memset(nu2, 0, sizeof(nu2));
        int cnt1 = 0, cnt2 = 0;
        for(int i = 1; i <= m1; ++i)
        {
            scanf("%d %d", u+i, v+i);
            nu1[u[i]][v[i]] = 1;
            nu1[v[i]][u[i]] = 1;
        }
        for(int i = 1; i <= m2; ++i)
        {
            scanf("%d %d", &x, &y);
            nu2[x][y] = 1;
            nu2[y][x] = 1;
        }
        for(int i = 1; i <= n; ++i)
        {
            mp[i] = i;
        }
        do
        {
            bool f1 = 0, f2 = 0;
            for(int i = 1; i <= m1; ++i)
            {
                    x = mp[u[i]];
                    y = mp[v[i]];
                    if(!nu1[x][y])  f1 = 1;
                    if(!nu2[x][y])  f2 = 1;
            }
            if(!f1) ++cnt1;
            if(!f2) ++cnt2;
 
        }while(next_permutation(mp + 1, mp + 1 + n));
      //  if(cnt1) cnt2 /= cnt1;
        printf("%d\n", cnt2 / cnt1);
    }
 
    return 0;
}