CODE [VS] 1009 产生数 (用Floyd算法求解传递闭包)

题目链接：

问题分析：很明显，扫描一遍字符串，遇到可以变换的数字，将这个可以变换的数字的所有可能情况的数目乘起来便是我们要的答案。现在的问题便是如何求解单个数字的所有可能情况。而这可以通过求解数字 0-9 之间的邻接矩阵的传递闭包的方法求解出来。用floyd算法即可。

ps：有人会问，floyd算法为何可以求解传递闭包？理由很简单，floyd算法可以求解出邻接矩阵中任意两个点之间的最短距离，，让一个邻接矩阵跑完floyd算法之后，再扫描一遍该邻接矩阵，如果两点(i -> j )之间的距离不为正无穷，那这两个点就是可达（i -> j）。

#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <algorithm>#include <queue>#include <map>#include <set>#include <stack>#include <sstream>#define PI acos(-1.0)const int inf = (1<<30) – 10;using namespace std;char str[35]; //用来存放 n ，因为数字 n 比较大，所以用字符串类型储存int f[11][11]; //存放数字 0 – 9 的邻接矩阵int sum[11]; //存放数字可以变化的情况数，比如sum[0]就是数字 ‘0’可以变化成其他数字的数目int m;void init() //初始化{for(int i = 0;i < 11; ++i){sum[i] = 0;for(int j = 0;j < 11; ++j){if(i == j){f[i][j] = 0;}else{f[i][j] = inf;}}}}void input() //输入{int x, y;scanf("%s%d",str,&m);for(int i = 0;i < m; ++i){scanf("%d%d",&x,&y);f[x][y] = 1;}}void floyd() //求解传递闭包{for(int k = 0;k <= 9; ++k){for(int i = 0;i <= 9; ++i){if(f[i][k])for(int j = 0;j <= 9; ++j){f[i][j] = min(f[i][j],f[i][k]+f[k][j]);}}}}void solved(){for(int i = 0;i <= 9; ++i)for(int j = 0;j <= 9; ++j)if(f[i][j] < inf)sum[i]++;//只要 i 与 j 之间可达（我这里的判断方法是，距离不为正无穷），sum[i] 便加一long long ans = 1;for(int i = 0; str[i] != '\0'; ++i){ans *= sum[str[i] – '0']; //组合数学，用乘法求解所有可能出现的情况}cout<<ans<<endl;}int main(){init(); ///初始化input(); ///输入数据floyd(); ///用Floyd算法求解传递闭包solved(); ///输出答案return 0;}如有BUG，欢迎指出！

天才是百分之一的灵感加上百分之九十九的努力