How many ways??-白红宇

How many ways??

阅读量：2038 次

发布时间：2019-04-28

本文共 1265 字，大约阅读时间需要 4 分钟。

题解：经典矩阵算法。把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，假设要求经过k步的路径数，我们仅仅须要二分求出A^k就可以。

参考文章：

/**@Author:   STZG*@Language: C++*/#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   //#define DEBUG#define RI register int#define endl "\n"using namespace std;typedef long long ll;//typedef __int128 lll;const int N=100000+10;const int M=100000+10;const int MOD=1e9+7;const double PI = acos(-1.0);const double EXP = 1E-8;const int INF = 0x3f3f3f3f;int t,n,m,k,p,l,r,u,v;int ans,cnt,flag,temp,sum;int s[25][25];int b[25][25];int a[25][25];char str;struct node{};void Matrix(int a[25][25],int b[25][25]){ int c[25][25]; memset(c,0,sizeof(c)); for(int i=0;i
                   
                    >=1; } return a[A][B];}int main(){#ifdef DEBUG freopen("input.in", "r", stdin); //freopen("output.out", "w", stdout);#endif //ios::sync_with_stdio(false); //cin.tie(0); //cout.tie(0); // while(~scanf("%d%d",&n,&m)&&n+m){ memset(s,0,sizeof(s)); for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); s[u][v]=1; } scanf("%d",&t); for(int i=1;i<=t;i++){ scanf("%d%d%d",&u,&v,&k); cout<
                    
                     <

转载地址：http://vqzof.baihongyu.com/

你可能感兴趣的文章

服务器端判断request来自Ajax请求(异步)还是传统请求(同步)