[정올 1021] 장난감 조립

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=300&sca=99 

JUNGOL

 

#include <stdio.h>

int mtr[101][101], N, M, est[101];

int IsMiddlePartRemain() {
	for (int i = 1; i < N; i++)
		if (mtr[N][i] && est[i] == 0) return 1;
	return 0;
}

int main(void) {
	scanf("%d", &N);
	scanf(" %d", &M);
	int UpDv, LwDv, num, i, j;
	for (i = 0; i < M; i++)	{
		scanf(" %d %d %d", &UpDv, &LwDv, &num);
		mtr[UpDv][LwDv] = num;
	}

	for (i = 1, j = 0; i < N; i++) {
		for (j = 1; j < N; j++)		
			if (mtr[i][j]) { 
				j = -1; break; 
			}
		if (j != -1) est[i] = 1;
	}

	while (IsMiddlePartRemain())
		for (int i = 1; i < N; i++)
			if (mtr[N][i] && est[i] == 0) {
				for (int j = 1; j < N; j++)	
					mtr[N][j] += mtr[i][j] * mtr[N][i];
				mtr[N][i] = 0;
			}

	for (int i = 1; i < N; i++)	
		if (mtr[N][i])	printf("%d %d\n", i , mtr[N][i]);

	return 0;
}