2014
01-26

# A Pair of Graphs

We say that two graphs are equivalent if and only if a one-to-one correspondence between their nodes can be established and under such a correspondence their edges are exactly the same. Given A and B, two undirected simple graphs with the same number of vertexes, you are to find a series of operations with the minimum cost that will make the two graphs equivalent. An operation may be one of the following two types:
a) Add an arbitrary edge (x, y), provided that (x, y) does not exist before such an operation. Such an operation costs IA and IB on two graphs, respectively.
b) Delete an existing edge (x, y), which costs DA and DB on two graphs,respectively.

There are multiple test cases in the input file.
Each test case starts with three integers, N, MA and MB, ( 1 ≤ N ≤ 8, 0 ≤ MB ,MA ≤ N*(N-1)/2 ), the total number of vertexes, the number of edges in graph A,and the number of edges in graph B, respectively. Four integers IA, IB, DA, and DB come next, (0 ≤ IA, IB, DA, DB ≤ 32767 ), representing the costs as stated in the problem description. The next MA + MB lines describe the edges in graph A followed by those in graph B. Each line consists of exactly two integers, X and Y ( X ≠ Y , 0 ≤ X,Y < N).
Two successive test cases are separated by a blank line. A case with N = 0, MA = 0,and MB = 0 indicates the end of the input file, and should not be processed by your program.

There are multiple test cases in the input file.
Each test case starts with three integers, N, MA and MB, ( 1 ≤ N ≤ 8, 0 ≤ MB ,MA ≤ N*(N-1)/2 ), the total number of vertexes, the number of edges in graph A,and the number of edges in graph B, respectively. Four integers IA, IB, DA, and DB come next, (0 ≤ IA, IB, DA, DB ≤ 32767 ), representing the costs as stated in the problem description. The next MA + MB lines describe the edges in graph A followed by those in graph B. Each line consists of exactly two integers, X and Y ( X ≠ Y , 0 ≤ X,Y < N).
Two successive test cases are separated by a blank line. A case with N = 0, MA = 0,and MB = 0 indicates the end of the input file, and should not be processed by your program.

1 0 0
1 2 3 7

4 2 3
1 6 5 1
0 1
0 3
0 2
1 2
1 0

0 0 0

Case #1: 0
Case #2: 1

#include <stdio.h>
#include <string.h>

int A[10][10],B[10][10];
int vary[10];
bool flag[10];

int small1,small2,min;

void action(int n)
{
int i,j,val=0;

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(A[vary[i]][vary[j]]==B[i][j])    continue;
if(A[vary[i]][vary[j]])
val+=small2;
else
val+=small1;
}
}
if(val<min)    min=val;
}

void DFS(int pos,int n)
{
int i;
if(pos==n)    {action(n);    return ; }

for(i=0;i<n;i++)
{
if(flag[i])
{
vary[pos]=i;
flag[i]=false;
DFS(pos+1,n);
// 原来->DFS(++pos,n);考，给力!递归中pos的值再回溯时，pos的值就变了...
// 狂汗!!
flag[i]=true;
}
}
}

void solve()
{
int n,Ma,Mb,Ia,Ib,Da,Db;
int i,a,b,cas=0;

while(scanf("%d %d %d",&n,&Ma,&Mb) && n)
{
scanf("%d %d %d %d",&Ia,&Ib,&Da,&Db);
small1=(Ia<Db?Ia:Db);
small2=(Ib<Da?Ib:Da);
min=0xfffffff;

memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
for(i=0;i<Ma;i++)
{
scanf("%d %d",&a,&b);
A[a][b]=A[b][a]=1;
}
for(i=0;i<Mb;i++)
{
scanf("%d %d",&a,&b);
B[a][b]=B[b][a]=1;
}
for(i=0;i<n;i++)    flag[i]=true;

DFS(0,n);

printf("Case #%d: %d\n",++cas,min/2);
}
}

int main()
{
solve();
return 0;
}

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

2. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n