UVa 200 Rare Order

200    Rare Order    poao899    Accepted    C++    0.012    2009-12-12 11:28:09                            .


不難不過覺得好有趣(?

寫過太多奇怪的算法好久沒有好好想一題了雖然這是我的問題XD

算是...最短路...吧



找出相鄰兩列可以知道的大小關係

再去建圖

//*********************

//UVa 200
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 100000
struct alpha{
    int cha,rank,in,out;
    bool operator<(const alpha &b)const{
        return rank<b.rank;
    }
}A[30];
int dist[30][30],nlen,plen,st,cnt;
char S1[30],S2[30];
main(){
    char *now=S1,*pre=S2,*t;
    //Initialize
    for(int i=0;i<30;i++){
        A[i].cha='A'+i;
        for(int j=0;j<30;j++)
            dist[i][j]=INF;
    }
    //Input
    while(1){
        gets(now);
        if(now[0]=='#')break;
        nlen=strlen(now);
        for(int i=0;i<nlen&&i<plen;i++)
            if(now[i]!=pre[i]){
                dist[pre[i]-'A'][now[i]-'A']=-1;
                A[now[i]-'A'].in++;
                A[pre[i]-'A'].out++;
                break;
            }
        plen=nlen;
        t=now;now=pre;pre=t;
    }
    //Find Start
    for(int i=0;i<30;i++){
        if(A[i].in+A[i].out >0 && A[i].in==0){
            st=i;
            break;
        }
    }
    dist[st][st]=0;
    //Floyd-Warshall
    for(int k=0;k<30;k++)
        for(int i=0;i<30;i++)
            for(int j=0;j<30;j++)
                if(dist[i][k]+dist[k][j] < dist[i][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
    //Rank
    for(int i=0;i<30;i++){
        if(dist[st][i]<=0)
            A[i].rank=-dist[st][i];
        else A[i].rank=10000;
    }
    //Sort
    std::sort(A,A+30);
    //Output
    for(int i=0;i<30;i++){
        if(A[i].rank==10000)break;
        printf("%c",A[i].cha);
    }
    printf("\n");
}