「POJ1094」Sorting It All Out

题意：给定 $n$ 个变量，$m$ 个不等式。不等式之间具有传递性，即若 $A>B$ 且 $B>C$ ，则 $A>C$。判断这 $m$ 个不等式是否有矛盾。若存在矛盾，则求出 $t$ 的最小值，满足仅用前 $t$ 个不等式就能确定不等式之间存在矛盾。若无矛盾，则判断这 $m$ 个不等式是否能确定每一对变量之间的关系。若能，则求出 $t$ 的最小值，满足仅用前 $t$ 个不等式就能确定每一对变量之间的大小关系。

一道传递闭包的板子题。

对于每个 $i < j$ 的不等式，令 $d[i,j]=1$，如果是 $i>j$ 的不等式，看作 $j<i$ 处理，其余均设为 $0$。

用 $Floyd$ 传递闭包，如果 $d[i,j]=d[j,i]=1$，那么矛盾，如果 $d[i,j]=d[j,i]=0$ ，那么不能确认关系。

如果对于每个 $d[i,j]$ 和 $d[j,i]$，其中仅有一个为 $1$，说明可以确定关系，然后再用二分，判断是否能够仅用前 $t$ 个不等式求值。

最后输出答案可以发现，记录每个数的入度，入度从大到小对应着变量从小到大，根据入度直接暴力搜索输出即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,flag;
int dis[31][31],deg[31];
char s[4];
int judge()//1为已经排序好,0为矛盾,-1为无法确定顺序
{
	int mark=1;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			if(dis[i][j]&&dis[j][i])
				return 0;
			else if(!dis[i][j]&&!dis[j][i])
				mark=-1;
		}
	return mark;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF&&n+m)
	{
		memset(dis,0,sizeof(dis));
		memset(deg,0,sizeof(deg));
		for(int i=1;i<=n;i++)
			dis[i][i]=1;
		flag=0;
		for(int t=1;t<=m;t++)
		{
			scanf("%s",s+1);
			if(flag)
				continue;
			int x=s[1]-'A'+1;
			int y=s[3]-'A'+1;
			dis[x][y]=1;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					dis[i][j]|=dis[i][x]&dis[y][j];//传递闭包
			int ans=judge();
			if(ans==0)
			{
				printf("Inconsistency found after %d relations.\n",t);
				flag=1;//标记
				continue;
			}
			else if(ans==1)
			{
				printf("Sorted sequence determined after %d relations: ",t);
				for(int i=1;i<=n;i++)
					for(int j=i+1;j<=n;j++)
					{
						if(dis[i][j])
							deg[i]++;
						else
							deg[j]++;//注意统计入度！！
					}
				for(int i=n-1;i>=0;i--)
					for(int j=1;j<=n;j++)
						if(deg[j]==i)//入度的值可判断大小
							printf("%c",j+'A'-1);
				printf(".\n");
				flag=1;
				continue;
			}
		}
		if(!flag)
			printf("Sorted sequence cannot be determined.\n");
	}
	return 0;
}