PKU 1422. Air raid. WA -_-....

#include <stdio.h> int found[10001][10001]; int result[10001][10001]; int main() { int cases, inters, streets, start, end, i, j, k, l, sum; scanf("%d", &cases); while (cases--) { scanf("%d", &inters); scanf("%d", &streets); while (streets--) { scanf("%d%d", &start, &end); found[start][end] = 1; result[start][end] = 1; } for (i = 1; i < inters; i++) { for (j = 1; j <= inters; j++) { for (k = 1; k <= inters; k++) { if (result[j][k] == i) { for (l = 1; l <= inters; l++) { result[j][l] += found[k][l]; } } } } } for (i = 1; i <= inters; i++) { for (j = 1; j <= inters; j++) { sum = 0; for (k = 1; k <= inters; k++) { sum += found[j][k]; } if (sum != 0) { result[i][j] = 0; } else { sum = 0; for (k = 1; k <= inters; k++) { sum += found[k][i]; } if (sum != 0) { result[i][j] = 0; } else { result[i][j] = 1; } } } } sum = 0; for (i = 1; i <= inters; i++) { for (j = 1; j <= inters; j++) { sum += result[i][j]; } } printf("%d\n", sum); for (i = 1; i <= inters; i++) { for (j = 1; j <= inters; j++) { found[i][j] = 0; result[i][j] = 0; } } } return 0; } <SPAN id=tx_marker_caret></SPAN>

쉬바.... 신이시여..

-_-

역시 역무실에서 메모장 코딩에는 한계가 있는건가.

풀이는 간단합니다.

n개의 요소가 있는 그래프에서, 각 노드의 차수를 최소로 하는 신장트리를 구성하면 됩니다.

이렇게 하면 리프노드와 루트의 갯수가 최소화되어, 각 루트와 리프의 갯수만큼만 특공대를 투입하면 최소의 인원만

투입이 가능하지요.

여기서 주의할 점은, 단순히 신장트리가 되는것 뿐만 아니라, 상황에 따라서는 트리가 아닌 포레스트를 다뤄야 합니다.

이로 인해 다중 연결 리스트를 사용해 처리하게 되면 머리가 꽤나 아파집니다.

제 경우는 n개의 intersection에 대해 n * n의 행렬을 사용해 표현했습니다.

일단 found라는, 최초 입력에 따른 유향 그래프와, result라는, 연산 과정과 최종 연산 결과를 담을 2개의 배열을 사용했습니다.

1차로 found에 입력을 받고, 그 내용을 result에 카피합니다.

이후, 1개 거쳐서 가는 방법, 2개 거쳐서 가는 방법, 3개 걸쳐서 가는 방법, ..... n - 1개 거쳐서 가는 방법을 모두 표기합니다.

여기서 일단 n^3의 시간이 소요됩니다.

이 방법으로 나온 결과물에는 root to leaf의 경우와 그 중간 경로가 섞여져 들어가 있습니다.

여기서 다시한번 root to leaf가 아닌 경우를 모두 솎아냅니다.

root to leaf가 아닌 경우는 0으로, 맞는 경우는 전부 1로 바꿔버린 후,

result 안의 내용을 다 더해서 sum에 저장해 버립니다.

이렇게 되면, 자동으로 root to leaf의 갯수를 카운트 할 수 있게 되며, 이 카운트 한 값이 답입니다.

근데.... 왜 WA냐고 -_-