1009 产生数

 

2002年NOIP全国联赛普及组

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

 查看运行结果

 

 

题目描述 

Description

 

　　给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。

　　规则：

　　　一位数可变换成另一个一位数：

　　　规则的右部不能为零。

　　例如：n=234。有规则（k＝2）：

　　　　2－> 5

　　　　3－> 6

　　上面的整数 234 经过变换后可能产生出的整数为（包括原数）:

　　　234

　　　534

　　　264

　　　564

　　共 4 种不同的产生数

问题：

　　给出一个整数 n 和 k 个规则。

求出：

　　经过任意次的变换（0次或多次），能产生出多少个不同整数。

　　仅要求输出个数。

输入描述 

Input Description

 

键盘输人，格式为：

 　　n k

 　　x1 y1

 　　x2 y2

 　　... ...

 　　xn yn

输出描述 

Output Description

 

 屏幕输出，格式为：

　　一个整数（满足条件的个数）

 

样例输入 

Sample Input

 

　　 234 2

　 　2 5

 　　3 6

样例输出 

Sample Output

 

4

 

思路：

　　符合变换规则的数可以在变换一次后的新数仍然符合变换规则

　　所以我们考虑将之转化为一个图论问题

　　就是考虑从i到j需要经过多少点

　　经过的点的个数就是可以变换成的数

　　可是怎么求呢？

　　用弗洛伊德算法

　　弗洛伊德是个n^3的动态规划

　　枚举三个点i，j，k

　　如果i到j的距离大于i到k加上k到i的距离就会更新i到j的距离

　　根据这个原理我们可以增加一个计数器

　　即每更新一次i到j的距离则i的变换数的个数加1

　　因为n的本身也算是一种排列

　　所以所有数的变换个数初始为1、

　　将所有的变换数的个数都求出后

　　可以通过相乘的积得出总个数

 

来，上代码:

#include
          
           #include
           
            #include
            
             using namespace std;unsigned long long int ans=1,num[10];int n,map[10][10];char cur[50];int main(){    memset(map,127/3,sizeof(map));    int from,to;    scanf("%s",cur);    scanf("%d",&n);    //for(int i=0;i<=9;i++) num[i]=1;    for(int i=1;i<=n;i++)    {        scanf("%d%d",&from,&to);        map[from][to]=1;    }    for(int k=0;k<=9;k++)    {        for(int j=0;j<=9;j++)        {            for(int i=0;i<=9;i++)            {                if(i!=j&&j!=k&&k!=i)                if(map[j][k]+map[k][i]