1171.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 1171 on 2006-11-13 at 21:45:36 */
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 32;
 
int main()
{
	int n, m, g[N][N][N];
 
	for(int t = 0; scanf("%d", &m) != EOF; t++) {
		memset(g, 0, sizeof(g)); n = 0;
		for(int i = 0; i < m; i++) {
			int a, b; scanf("%d %d", &a, &b);
			n >?= a+1; n >?= b+1;
			g[0][a][b] = 1;
		}
		for(int k = 0; k < n; k++)
			for(int i = 0; i < n; i++)
				for(int j = 0; j < n; j++)
					g[k+1][i][j] = g[k][i][j]+g[k][i][k]*g[k][k][j];
		printf("matrix for city %d\n", t);
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++) {
				int can = false;
				for(int k = 0; k < n && !can; k++)
					if(g[n][i][k] > 0 && g[n][k][j] > 0 && g[n][k][k] > 0)
						can = true;
				if(can || (g[n][i][j] > 0 && g[n][j][i] > 0)) printf("-1");
				else printf("%d", g[n][i][j]);
				putchar(j == n-1 ? '\n' : ' ');
			}
	}
	
	return 0;
}