UVA - 125 Numbering Paths

1338 단어
제목: N 개의 점 관계 행렬을 구합니다. 행렬은 경로의 개수를 기록합니다. N은 입력의 최대 값에 1을 추가합니다. 만약 개수에 무한 횟수가 존재한다면 인쇄-1, dp[i][i]를 통과하는 무한 횟수가 존재하는지 여부입니다!판단
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 30;

int n,m,dp[MAXN][MAXN];

void floyd(){
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dp[i][j] += dp[i][k] * dp[k][j];
    for (int k = 0; k < n; k++)
        if (dp[k][k])
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dp[i][k] && dp[k][j])
                        dp[i][j] = -1;
}

void print(){
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf("%d%c",dp[i][j],(j==n-1)?'
':' '); } int main(){ int t = 0; while (scanf("%d",&m) != EOF){ n = 0; memset(dp,0,sizeof(dp)); printf("matrix for city %d
",t++); while (m--){ int a,b; scanf("%d%d",&a,&b); dp[a][b] = 1; n = max(n,max(a,b)); } n++; floyd(); print(); } return 0; }

좋은 웹페이지 즐겨찾기