首页 > 代码库 > poj 1094

poj 1094

2024-07-07 15:57:32   229人阅读

唉  这几天有点热 有点烦躁 以后能做成什么样。。。。 

题意：给定n个字母《0+A,...n+A》 和m个关系 想x>y  问是否能唯一确定他们的大小关系

1  在第几个关系能确定他们的排序 就输出这个位置和排序

2 如果出现矛盾就输出矛盾的位置

3 整个关系输入之后还不能确定则输出不能确定关系

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<cstring>
using namespace std;
int map[55][55];
int in[55];
int jie[55];
int n;
int sort()//1  不能排序  ;  2 能排序
{
    int ji[55];
    int f=2;
//  memset(s,0,sizeof(s));
    int i,j;
    int x,sum;
    for(i=1;i<=n;i++)
        ji[i]=in[i];
    for(i=1;i<=n;i++)
    {
        sum=0;
        for(j=1;j<=n;j++)
            if(ji[j]==0)
            {
                sum++;
                x=j;
            }
        if(sum==0) return 1;   //是否有环
        if(sum>1) f=0;
        jie[i]=x;
        ji[x]=-1;
        for(j=1;j<=n;j++)
            if(map[x][j])
                ji[j]--;
    }
    return f;
}
int main()
{
    int yes,i;
    char s[11];
    int m;
    while(cin>>n>>m)
    {
        yes=0;
        if(n==0&&m==0)
            break;
        memset(in,0,sizeof(in));
        memset(map,0,sizeof(map));
        for(i=1;i<=m;i++)
        {
            cin>>s;
            if(yes) continue;
            int u=s[0]-‘A‘+1;
            int v=s[2]-‘A‘+1;
            if(s[1]==‘<‘)
            {
                if(map[v][u])
                {
                    cout<<"Inconsistency found after "<<i<<" relations."<<endl;
                    yes=1;
                    continue;
                }
                map[u][v]=1;
                in[v]++;
            }
            else
            {
                if(map[u][v])
                {
                    cout<<"Inconsistency found after "<<i<<" relations."<<endl;
                    yes=1;
                    continue;
                }
                map[v][u]=1;
                in[u]++;
            }
            int x=sort();
            if(x==1)
            {   cout<<"Inconsistency found after "<<i<<" relations."<<endl;
                    yes=1;
                    continue;
            }
            if(x==2)
            {
                cout<<"Sorted sequence determined after "<<i<<" relations: ";
                for(int j=1;j<=n;j++)
                    cout<<(char)(jie[j]-1+‘A‘);
                cout<<‘.‘<<endl;
                yes=1;
            }
        }
     
        if(!yes)
            cout<<"Sorted sequence cannot be determined."<<endl;
    }
    return 0;
}

 


联系
我们