题意：
给你一些a<b的关系，然后有三组询问。
1 当前这组之后如果能确定这n个数的大小关系，那么就输出关系
2 当前时候出现bug，就是和前面如果冲突，那么就不行
3 最后的答案是否是不确定的，就是既没确定关系，也没出现bug.
思路：
这个题目要清楚一点就是处理顺序，上面的三个情况可能会出现重叠的情况，那么就按照上面的1 2 3的优先级来处理，至于判断当前关系是否成立和唯一我用的是差分约束，没有用拓扑排序，差分约束跑完最短路（或者最长路）没有死环，就证明没有bug，而任意点到起点的距离都不重复，那么就是唯一，否则就是当前不能确定，还有就是讨论组里面有个人给了两组数据，我觉得很有用，我就直接粘贴过来吧，为了大家方便理解题意。
分享两组关键性数据:
Posted by MyTalent at 2013-05-08 23:24:07 on Problem 1094
6 6
A<F
B<D
C<E
F<D
D<E
E<F
output：
Inconsistency found after 6 relations.
5 5
A<B
B<C
C<D
D<E
E<A
output:
Sorted sequence determined after 4 relations: ABCDE
第一个例子讲述的是：矛盾和多选，优先判断是否矛盾
第二个例子讲述的是：在矛盾之前如果有成功的，算是成功
#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N_node 30
#define N_edge 1000
#define INF 100000000
using namespace std;
typedef struct
{
int to ,cost ,next;
}STAR;
typedef struct
{
int id ,v;
}ANS;
int list[N_node] ,tot;
int mks[N_node] ,mkt[N_node];
int s_x[N_node];
char str[1000+5][5];
STAR E[N_edge];
ANS ans[N_edge];
void add(int a ,int b ,int c)
{
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
}
bool camp(ANS a ,ANS b)
{
return a.v < b.v;
}
bool Spfa(int s ,int n)
{
for(int i = 0 ;i <= n ;i ++)
s_x[i] = INF;
memset(mks ,0 ,sizeof(mks));
memset(mkt ,0 ,sizeof(mkt));
queue<int>q;
q.push(s);
s_x[s] = 0;
mks[s] = mkt[s] = 1;
while(!q.empty())
{
int xin ,tou;
tou = q.front();
q.pop();
mks[tou] = 0;
for(int k = list[tou] ;k ;k = E[k].next)
{
xin = E[k].to;
if(s_x[xin] > s_x[tou] + E[k].cost)
{
s_x[xin] = s_x[tou] + E[k].cost;
if(!mks[xin])
{
mks[xin] = 1;
if(++mkt[xin] >= n) return 0;
q.push(xin);
}
}
}
}
return 1;
}
bool judeok(int n ,int id)
{
for(int i = 1 ;i <= n ;i ++)
{
ans[i].id = i;
ans[i].v = s_x[i];
}
sort(ans + 1 ,ans + n + 1 ,camp);
for(int i = 2 ;i <= n ;i ++)
if(ans[i].v == ans[i-1].v)
return 0;
printf("Sorted sequence determined after %d relations: " ,id);
for(int i = 1 ;i <= n ;i ++)
printf("%c" ,ans[i].id + 'A' - 1);
printf(".\n");
return 1;
}
int main ()
{
int n ,m ,i;
while(~scanf("%d %d" ,&n ,&m) && n + m)
{
for(i = 1 ;i <= m ;i ++)
scanf("%s" ,str[i]);
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= n ;i ++)
add(0 ,i ,0);//虚拟出来一个0点，连接所有点，为了防止整个图不是连通的
for(i = 1 ;i <= m ;i ++)
{
int a = str[i][0] - 'A' + 1;
int b = str[i][2] - 'A' + 1;
add(b ,a ,-1);
int now = Spfa(0 ,n);
if(now && judeok(n ,i)) break;
if(!now)
{
printf("Inconsistency found after %d relations.\n" ,i);
break;
}
}
if(i == m + 1)
{
printf("Sorted sequence cannot be determined.\n");
continue;
}
}
return 0;
}