题目描述 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<cstdio> #include<cstring> #include<iostream> 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]<map[j][i]) { map[j][i]=map[j][k]+map[k][i]; } } } } //for(int i=0;i<=9;i++) cout<<num[i]<<" "; //cout<<endl; for(int i=0;i<=9;i++) { num[i]++; for(int j=0;j<=9;j++) { if(j==i) continue; if(map[i][j]<10000) num[i]++; } } for(int i=0;i<strlen(cur);i++) ans=(ans*num[(int)(cur[i]-'0')]); cout<<ans<<endl; return 0; }