hdu 1625(floyd判环）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1625、

思路：大牛说是floyd判环，一想确实如此，我还一直在想如果用记忆化的怎么处理环呢...orz....

首先通过Floyd预处理，把所有的路径数求出来，即d[i][j] += d[i][k] * d[k][j]。然后确定有无环，如果存在环的话，即d[k][k] != 0（存在环），那么所有的点i，j，只要经过了k（i->k->j），那么它的路径数是不能确定的，反之，确定。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 55
int path[MAXN][MAXN];
int m,n;

void floyd(){
    for(int k=0;k<=n;k++){
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                path[i][j]+=path[i][k]*path[k][j];
            }
        }
    }
    for(int i=0;i<=n;i++)if(path[i][i]){
        path[i][i]=-1;
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                if(path[j][i]&&path[i][k]){
                    path[j][k]=-1;
                }
            }
        }
    }
}

int main(){
    int u,v,t=0;
    while(~scanf("%d",&m)){
        memset(path,0,sizeof(path));
        n=0;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            path[u][v]=1;
            n=max(n,max(u,v));
        }
        printf("matrix for city %d\n",t++);
        floyd();
        for(int i=0;i<=n;i++){
            for(int j=0;j<n;j++){
                printf(" %d",path[i][j]);
            }
            printf(" %d\n",path[i][n]);
        }
    }
    return 0;
}