1094:Sorting It All Out

keyword

Warshall-Floyd　C++

概要

3660:Cow Contestとほとんど同じ内容。
A

int main(){
    bool contr, found;
    int bigger[30][30], smaller[30][30];
    int i,j,k,l,n,m,ans,pos,x,y,rept=0;
    char a, op, b;
    char str[30];

    while(scanf("%d %d\n", &n, &m)!=EOF){
        if(!(n||m)) break;
        if(rept++)printf("\r\n");
        REP(i,n)REP(j,n) bigger[i][j] = smaller[i][j] = 1<<21;
        contr = false;
        found = false;
        REPONE(l,m){
            scanf("%c%c%c\n",&a,&op,&b);
            if(contr || found) continue;
            if(op=='>') swap(a,b);
            x = a - 'A';
            y = b - 'A';
            if(x==y) contr = true;
            if(bigger[x][y] == 0 || smaller[y][x] == 0){
                contr = true;
                ans = l;
            }
            bigger[y][x] = smaller[x][y] = 0;
            REP(k,n)REP(i,n)REP(j,n)
                bigger[i][j] = min(bigger[i][j],bigger[i][k]+bigger[k][j]);
            REP(k,n)REP(i,n)REP(j,n)
                smaller[i][j] = min(smaller[i][j],smaller[i][k]+smaller[k][j]);
            if(!contr)REP(i,n)REP(j,n)if(!bigger[i][j] && !smaller[i][j]){
                contr = true;
                ans = l;
            }
            REP(i,n){
                int cnt = 0;
                REP(j,n){
                    if(bigger[i][j] == 0 && smaller[i][j] == 0) contr = true;
                    else if(((bigger[i][j] == 0) ^ (smaller[i][j] == 0))) cnt++;
                }
                if(cnt != n-1) break;
            }
            if(!found && i==n){
                found = true;
                ans = l;
            }
            if(!contr )REP(i,n)if(bigger[i][i] == 0 || smaller[i][i] == 0){
                contr = true;
                ans = l;
            }
        }
        if(contr) printf("Inconsistency found after %d relations.",ans);
        else if(found){
            printf("Sorted sequence determined after %d relations: ", ans);
            pos = 0;
            REP(j,n)REP(i,n){
                if(count(bigger[i], bigger[i]+n, 0) == j){
                    str[pos++] = (char)(i + 'A');
                    break;
                }
            }
            str[pos] = '\0';
            printf("%s.", str);
        }
        else printf("Sorted sequence cannot be determined.");
    }

    return 0;
}