2254.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2254 on 2006-05-29 at 10:23:55 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int PN = 128;

int main()
{
	int ps[PN][PN], n, i, j, k, st[PN][2];
	bool w[PN][PN];
	
	while(scanf("%d", &n) != EOF) {
		memset(w, false, sizeof(w));
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) {
				scanf("%d", &ps[i][j]);
				if(ps[i][j] == 1) w[i][j] = true;
				else if(ps[i][j] == -1) w[j][i] = true;
				if(i == j) ps[i][j] = 1;
			}
		for(k = 0; k < n; k++)
			for(i = 0; i < n; i++)
				for(j = 0; j < n; j++)
					w[i][j] = w[i][j] || (w[i][k] && w[k][j]);
		memset(st, 0, sizeof(st));
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(ps[i][j] == 0 && w[i][j]) { st[i][0]++; st[j][1]++; }
		for(i = 0; i < n; i++) printf("%d %d\n", st[i][0], st[i][1]);
		putchar('\n');
	}
	
	return 0;
}