题目描述

给定 n 个变量和 m 个不等式。其中 n 小于等于 26，变量分别用前 n 的大写英文字母表示。

不等式之间具有传递性，即若 A>B 且 B>C，则 A>C。

请从前往后遍历每对关系，每次遍历时判断：

如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
如果发生矛盾，则结束循环，输出有矛盾；
如果循环结束时没有发生上述两种情况，则输出无定解。

答案

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
bool ai[300][300],answer,p,ifor;
int ans[30],q,n,m;
bool st[300];
int main()
{
    while(scanf("%d%d\n",&n,&m),m)
    {
        answer=0;ifor=0;
        memset(ai,0,sizeof(ai));
        memset(ans,0,sizeof(ans));
        memset(st,0,sizeof(st));
        for(int i=1;i<=m+1;i++)
        {
            if(i<=m)
            {
                if(!ifor)q=i;
                int a,b,c;
                scanf("%c%c%c\n",&a,&c,&b);
                if(c=='>')swap(a,b);
                ai[a][b]=true;
                for(int j='A';j<='A'+n-1;j++)
                    ai[a][j]|=ai[a][b]&ai[b][j],
                    ai[j][b]|=ai[a][b]&ai[j][a];
                for(int i='A';i<='A'+n-1;i++)
                {
                    int a=n;
                    for(int j='A';j<='A'+n-1;j++)if(ai[i][j])a--;
                    if(!st[i])ans[a]=i,st[i]=true;
                }
            }
            int res=1;
            for(int i=1;i<=n;i++)if(!ans[i])res=0;
            if(res&&i<=m)ifor=1;
        else 
            if(res&&i>m&&!answer)
            {
                printf("Sorted sequence determined after %d relations: ",q);
                for(int i=1;i<=n;i++)printf("%c",ans[i]);
                printf(".\n");
            }
        else
            if(i<=m)
            {
                for(int h='A';h<='A'+n-1;h++)
                    for(int j=h+1;j<='A'+n-1;j++)
                    {
                        if(!ai[h][j]&&!ai[j][h]) p=0;
                        if(ai[h][j]+ai[j][h]==2&&!answer)
                            printf("Inconsistency found after %d relations.\n",i),answer=1;
                        memset(ans,0,sizeof(ans));
                        memset(st,0,sizeof(st));
                    }
            }
        else
            if(!p&&!answer)
                printf("Sorted sequence cannot be determined.\n"),answer=1;
        }
    }   
    return 0;
}

以下为题解

        answer=0;//记录是否有矛盾
        ifor=0;//记录是否已经可以找到答案
        memset(ai,0,sizeof(ai));//bool矩阵
        memset(ans,0,sizeof(ans));//用来储存答案
        memset(st,0,sizeof(st));//确保某一位没有值

         for(int i=1;i<=m+1;i++)
         //这只是为了合并代码，并没有特殊意义
         //如果愿意可以拆开
         if(i<=m)
         //范围内查询

                if(!ifor)q=i;//如果没有找到，先赋值
                int a,b,c;
                scanf("%c%c%c\n",&a,&c,&b);//输入
                if(c=='>')swap(a,b);//只储存"<"
                ai[a][b]=true;//储存a<b
                for(int j='A';j<='A'+n-1;j++)
                    ai[a][j]|=ai[a][b]&ai[b][j],
                    ai[j][b]|=ai[a][b]&ai[j][a];
                /*
                    找与a<b有关的已有比较
                    如：
                    如果a<b且b<j 则a<j
                    即:
                    ai[a][j]|=ai[a][b]&ai[b][j]
                    同样地
                    如果a>b且a>j 则b>j
                    即:
                    ai[j][b]|=ai[a][b]&ai[j][a];
                */

                for(int i='A';i<='A'+n-1;i++)
                //这是一个特别奇妙的思路
                {
                    int a=n;//假设i比谁都大
                    for(int j='A';j<='A'+n-1;j++)
                    if(ai[i][j])//但凡找到一个比i大的数就记录
                    a--;//排行减一
                    if(!st[i])ans[a]=i，//记录i的排行
                    st[i]=true;//他以有了排行
                }

            int res=1;
            for(int i=1;i<=n;i++)if(!ans[i])res=0;
            //找是否每一个数都有一个排行

            if(res&&i<=m)ifor=1;
            //记录什么时候找到的答案

            if(res&&i>m&&!answer)
            {
                printf("Sorted sequence determined after %d relations: ",q);
                for(int i=1;i<=n;i++)printf("%c",ans[i]);
                printf(".\n");
            }
            //可以输出结果了

            if(i<=m)
            {
                for(int h='A';h<='A'+n-1;h++)
                    for(int j=h+1;j<='A'+n-1;j++)
                    {
                        if(!ai[h][j]&&!ai[j][h]) p=0;
                        if(ai[h][j]+ai[j][h]==2&&!answer)
                        //a<b且b>a 便输出矛盾
                            printf("Inconsistency found after %d relations.\n",i),
                            answer=1;//记录已有矛盾
                        memset(ans,0,sizeof(ans));
                        memset(st,0,sizeof(st));
                    }
            }

            if(!p&&!answer)
                printf("Sorted sequence cannot be determined.\n"),answer=1;
            //最后判断是否有无数解