首页 > ACM题库 > HDU-杭电 > hdu 2464 A Pair of Graphs-DFS-[解题报告]C++
2014
01-26

hdu 2464 A Pair of Graphs-DFS-[解题报告]C++

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

题意:给出顶点数一样俩个图A、B 。试着给A、B添边或去边操作(给出A、B添、去边的代价)使最小的代价使A,B两图看着一样!

该题是2011-11-6周赛的题,当时AC率这个最高了,所以去做这个了,当把题意读懂时发现,这、、、根本无法解决!!

无奈之下放弃了,没注意n的范围,也不敢想暴力!最有C小加搜了解题报告,说都是暴力枚举。然后我就试试暴力了,可是如何暴呢?仍是没思路、、、、、没办法只有看解题报告了。现在算是明白了、、、、、!一个通过率最高的题就不会做,这说明什么?JUST WATER!

思路:暴力枚举(用到的是排列)。假设A、B两图经过操作两图一样了。那么此时一定存在:A的点与B的点一一对应!介于此,所以我们列出A、B各点一一对应的所有可能(而这就是排列 n!中情况),从中找到最小的花费。

 

代码:

#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;
}

本来看了别人的解题,自己就写出来了,可就是过不了。。。最好发现了在递归DFS中 ++pos是错的!!

解题转自:http://www.cnblogs.com/fornever/archive/2011/11/07/2240188.html


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

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