UVA125题解

秘密管理员 · 2019-10-05 09:10:20 · 题解

作为洛谷第一个通过这道题的辣鸡，我来发发题解

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;

const int N = 50;
typedef long long ll;
int n, G[N][N], Max;

void input() {
    memset(G, 0, sizeof(G));
    int a, b;
    Max = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a, &b); 
        if (a > Max) Max = a;
        if (b > Max) Max = b;
        G[a][b] = 1;
    }
}   
void warshall() {
    for (int k = 0; k <= Max; k++) {
        for (int i = 0; i <= Max; i++) {
            for (int j = 0; j <= Max; j++) {
                G[i][j] += G[i][k] * G[k][j];
            }
        }   
    }
    for (int k = 0; k <= Max; k++) {
        if (G[k][k]) {
            for (int i = 0; i <= Max; i++) {
                for (int j = 0; j <= Max; j++) {
                    if (G[i][k] & G[k][j]) G[i][j] = -1;    
                }   
            }
        }
    }
}

int main() {
    int Case = 0;
    while (scanf("%d", &n) != EOF) {
        printf("matrix for city %d\n", Case++);
        input();    
        warshall();
        for (int i = 0; i <= Max; i++) {
            for (int j = 0; j <= Max; j++) {
                if (j != 0) printf(" ");
                printf("%d", G[i][j]);  
            }puts("");
        }       
    }       
    return 0;
}