圖的最短路徑——Floyd例題

産生數

題目描述 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

分析

本題乍一看并沒有明顯的圖更沒有，是以本題的點（Key）在于發現隐含在題目中的圖，或者說自己建圖。

細心觀察還是可以發現圖的 如題文

變換規則

　           2－> 5

　　　　3－> 6

這裡寫成方向箭頭具有明顯的指向性 。

規則數<=15

數字一共10個 那麼小于等于15 意味着肯定不能局限于一對一的關系。

由此看來數字之間存在網狀的對應關系，而網狀結構即是圖，且為有向圖。

反觀題目整體，一個大體的思路是：由于數字長度頗大，是以以字元串讀入，産生數的總情況數目可以根據機率論排列組合的原理，總數目即是每位數字可能變化的種類之積。即按順序檢索每一位，檢視每一位有多少種可能的變化，并将每一位變化的可能數目相乘即為目标所求。

現在問題在于如何揪出每一位數字變化的可能數。顯然若1可以變化為5，則存在一條由1指向5的單向路徑，若此時有一種規則是5 - >7，說明一條由5指向7的單向路徑，同時存在一條由1指向5再指向7的單向路徑。那麼如果出現一個數位上的數字是1，對應的可能性就是5和7這兩種，即該位數變化的可能數為2.。這個問題就可以轉為求我們剛剛建構的那張有向圖的連通性。求有向圖的連通性，我們自然就可以使用Floyd算法。

Floyd算法部落格連結：https://blog.csdn.net/createprogram/article/details/86710519

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int dis[10][10];
long long ans=1,jishu=1;
int main()
{ string x;
  int k,x1,x2;
  cin>>x;
  cin>>k;
  for(int i=0;i<=9;i++)
  { for(int j=0;j<=9;j++)
    {if(i==j)  dis[i][j]=0;
     else dis[i][j]=INF;
    }
  }
  while(k--)
  { cin>>x1>>x2;dis[x1][x2]=1;
  }
  for(int k=0;k<=9;k++)//FLOYD算法 
  for(int i=0;i<=9;i++)
  for(int j=0;j<=9;j++)
  { if(i!=k&&j!=k&&i!=j)
    { dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    }
  }
  for(int i=0;i<x.length();i++)
  { jishu=1;
   for(int j=0;j<=9;j++)
    { if((dis[x[i]-'0'][j]!=INF)&&(dis[x[i]-'0'][j]!=0))
      { jishu++;
      }
    }
    ans*=jishu;
  }
  cout<<ans<<endl; 
  
}