UVA125 - Numbering Paths(floyd）

UVA125 - Numbering Paths(floyd）

UVA125 - Numbering Paths

题目大意： 
给m条有方向的边，然后要求你给出N * N的矩阵，矩阵G【i】【j】代表的是i到j之间的总路径数，如果i到j之间存在着环，那么G【i】【j】 = -1.

解题思路： 
i到j的路径数目等于i到k乘以k到j（经过k到达的话）。用floyd可以求出i到j之间的所有的路径数目，G【i】【j】 += G【i】【k】 * G【k】【j】；如果i，j之间存在着环,那么必然会存在一点i使得G【i】【i】 ！= 0.

代码：

#include <cstdio>
#include <cstring>const int maxn = 35;int N, M;
int G[maxn][maxn];int max (int a, int b) {return a > b ? a: b;
}
void floyd () {for (int k = 0; k <= N; k++)for (int i = 0; i <= N; i++)for (int j = 0; j <= N; j++)if (G[i][k] && G[k][j]) G[i][j] += G[i][k] * G[k][j];           for (int k = 0; k <= N; k++)if (G[k][k]) {for (int i = 0; i <= N; i++)for (int j = 0; j <= N; j++)if (G[i][k] && G[k][j])G[i][j] = -1;}
}int main () {int u, v;int T = 0;while (scanf("%d", &M) != EOF) {memset(G, 0, sizeof(G));N = 0;for (int i = 0; i < M; i++) {scanf ("%d%d", &u, &v);G[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++) {if (j != N)printf ("%d ", G[i][j]);elseprintf ("%d\n", G[i][j]);}   }return 0;
}