joj 2630: A Pair of Graphs（同构图的判定）

http://acm.jlu.edu.cn/joj/showproblem.php?pid=2630&off=2600

此题是2008年杭州赛区的第一道题，题意其实就是同构图的判定问题。根据数据量，枚举是个可行的办法。代码如下：

View Code

 1 #include <stdio.h>
 2 #include <memory.h>
 3 #define MAX 1<<30
 4 int ca=1,n,ma,mb,ia,ib,da,db;
 5 int mincost,vis[9],map_v[9],edge_a[9][9],edge_b[9][9];
 6 int min(int a,int b,int c,int d)
 7 {
 8     if(a<=b&&a<=c&&a<=d)return a;
 9     if(b<=a&&b<=c&&b<=d)return b;
10     if(c<=a&&c<=b&&c<=d)return c;
11     return d;
12 }
13 void dfs(int step)
14 {
15     if(mincost==0)return;//可能会提高速度的剪枝
16     if(step==n)
17     {
18         int i,j,dif_ma=ma,dif_mb=mb;
19         for(i=0;i<n;i++)
20         {
21             for(j=i+1;j<n;j++)
22             {
23                 if(edge_b[i][j]&&edge_a[map_v[i]][map_v[j]])
24                 {
25                     dif_ma--;
26                     dif_mb--;
27                 }
28             }
29         }
30         int cur_mincost = min(dif_mb*ia+dif_ma*ib,dif_ma*da+dif_mb*db,dif_ma*da+dif_mb*ia,dif_mb*db+dif_ma*ib);
31         if(cur_mincost<mincost)mincost = cur_mincost;
32         return;
33     }
34     int j;
35     for(j=0;j<n;j++)
36     {
37         if(!vis[j])
38         {
39             vis[j] = 1;
40             map_v[step] = j;
41             dfs(step+1);
42             vis[j] = 0;
43         }
44     }
45 }
46 int main()
47 {
48     int i;
49     while(scanf("%d%d%d",&n,&ma,&mb),n+ma+mb)
50     {
51         memset(edge_a,0,sizeof(edge_a));
52         memset(edge_b,0,sizeof(edge_b));
53         scanf("%d%d%d%d",&ia,&ib,&da,&db);
54         for(i=0;i<ma;i++)
55         {
56             int a,b;
57             scanf("%d%d",&a,&b);
58             edge_a[a][b]=edge_a[b][a] = 1;
59 
60         }
61         for(i=0;i<mb;i++)
62         {
63             int a,b;
64             scanf("%d%d",&a,&b);
65             edge_b[a][b]=edge_b[b][a] = 1;
66         }
67         mincost = MAX;
68         memset(vis,0,sizeof(vis));
69         for(i=0;i<n;i++)map_v[i]=i;
70         dfs(0);
71         printf("Case #%d: %d\n",ca++,mincost);
72     }
73     return 0;
74 }

另外，C++ STL有生成排列数的库函数，效率比一般自己编写的要高，试过之后，速度果然有提高。代码如下：

View Code

 1 #include <iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 #define MAX 1<<30
 5 int ca=1,n,ma,mb,ia,ib,da,db;
 6 int mincost,map_v[9],edge_a[9][9],edge_b[9][9];
 7 int min(int a,int b,int c,int d)
 8 {
 9     if(a<=b&&a<=c&&a<=d)return a;
10     if(b<=a&&b<=c&&b<=d)return b;
11     if(c<=a&&c<=b&&c<=d)return c;
12     return d;
13 }
14 int main()
15 {
16     int i;
17     while(scanf("%d%d%d",&n,&ma,&mb),n+ma+mb)
18     {
19         memset(edge_a,0,sizeof(edge_a));
20         memset(edge_b,0,sizeof(edge_b));
21         scanf("%d%d%d%d",&ia,&ib,&da,&db);
22         for(i=0;i<ma;i++)
23         {
24             int a,b;
25             scanf("%d%d",&a,&b);
26             edge_a[a][b]=edge_a[b][a] = 1;
27         }
28         for(i=0;i<mb;i++)
29         {
30             int a,b;
31             scanf("%d%d",&a,&b);
32             edge_b[a][b]=edge_b[b][a] = 1;
33         }
34         mincost = MAX;
35         int map_v[8]={0,1,2,3,4,5,6,7};
36         do
37         {
38             int i,j,dif_ma=ma,dif_mb=mb;
39             for(i=0;i<n;i++)
40             {
41                 for(j=i+1;j<n;j++)
42                 {
43                     if(edge_b[i][j]&&edge_a[map_v[i]][map_v[j]])
44                     {
45                         dif_ma--;
46                         dif_mb--;
47                     }
48                 }
49             }
50             int cur_mincost = min(dif_mb*ia+dif_ma*ib,dif_ma*da+dif_mb*db,dif_ma*da+dif_mb*ia,dif_mb*db+dif_ma*ib);
51             if(cur_mincost<mincost)mincost = cur_mincost;
52         }while (next_permutation(map_v,map_v+n));
53         printf("Case #%d: %d\n",ca++,mincost);
54     }
55 }