python/TangDou/AcWing/Floyd/UVA125.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 30;
int m, n, t;
int dp[N][N];

void floyd() {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dp[i][j] += dp[i][k] * dp[k][j]; //记录边数
}

int main() {
    while (scanf("%d", &m) != EOF) {
        int a, b;
        n = 0;
        memset(dp, 0, sizeof(dp));

        while (m--) {
            scanf("%d%d", &a, &b);
            dp[a][b] = 1;       //单向边，同时边权为1
            n = max({n, a, b}); //最大节点号
        }

        //注意有0节点，所以矩阵边长为n+1。
        n++;

        floyd();

        printf("matrix for city %d\n", t++);

        //结论：某个节点到自己的距离不为0，就是有环
        for (int k = 0; k < n; k++)
            if (dp[k][k]) { //如果存在环的话，需要特殊处理
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        if (dp[i][k] && dp[k][j]) //如果有其它点i,j利用过k，则i->k,k->j都是无数条路径
                            dp[i][j] = -1;
                dp[k][k] = -1; //标识k->k也有无数条路径
            }

        //严格控制格式，输出矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                if (j == 0)
                    printf("%d", dp[i][j]);
                else
                    printf(" %d", dp[i][j]);
            puts("");
        }
    }
    return 0;
}