POJ1094查分约束，判断关系是否唯一

题意：

给你一些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;

}