问题描述

给你N个变量,M个不等式(形如x<y),需要你判断:1.他们是否矛盾 2.若无矛盾,则是否能确定每个变量的关系 3.若能,则求出用前x个不等式就能求出关系x的最小值。

输入

有多组数据,每组数据第一行n,m。当n=0且m=0时输入结束。
下面m行给出m个不等式。

输出

对于每组数据输出下面三句话中的一句:
Sorted sequence determined after xxx relations: yyy…y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

思路

求这些约束关系的当然是用拓扑排序啦。

拓扑排序时如果有两个或以上的点入度为0,则这个序列不能确定,如果没有一个入度为0的点,则这是矛盾的。然后每增加一个不等式时都进行一遍拓扑排序。

考虑输出,我们开一个数组记录这些变量,拓扑排序时按照拓扑序将这些变量加进数组,这样数组内的元素就一定时从大到小的。

细节

  1. 要注意输出格式
  2. 如果成功了,但以后的关系出现矛盾依然认为它成功
  3. 每一组数据要把输入读完

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 30
using namespace std;

int n, m, tag, top, pos, cnt, flag1, flag2, q[MAXN], deg[MAXN], temp[MAXN];
bool f[MAXN][MAXN];
char t[5];

int topo()
{
    top=0; flag2=1;
    for(int i=1; i<=n; i++) temp[i]=deg[i];
    for(int i=1; i<=n; i++)
    {
        cnt=0;
        for(int j=1; j<=n; j++)
            if(temp[j]==0) {cnt++; pos=j;}
        if(cnt==0) return 0;
        if(cnt>1) flag2=-1;
        q[top++]=pos;
        temp[pos]=-1;
        for(int j=1; j<=n; j++)
            if(f[pos][j]==1) temp[j]--;
    }
    return flag2;
}

int main()
{
    scanf("%d%d", &n, &m);
    while(n!=0 && m!=0)
    {
        memset(f, 0, sizeof(f));
        memset(deg, 0, sizeof(deg));
        flag1=false;
        for(int i=1; i<=m; i++)
        {
            scanf("%s", t);
            if(flag1) continue;
            int x=t[0]-'A'+1, y=t[2]-'A'+1;
            f[x][y]=true; deg[y]++;
            tag=topo();
            if(tag==0)
            {
                printf("Inconsistency found after %d relations.\n",i);
                flag1=1;
            }
            if(tag==1)
            {
                printf("Sorted sequence determined after %d relations: ",i);
                for(int j=0; j<n; j++) printf("%c", q[j]+'A'-1);
                printf(".\n");
                flag1=1;
            }
        }
        if(!flag1) printf("Sorted sequence cannot be determined.\n");
        scanf("%d%d", &n, &m);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注