算法竞赛进阶指南，360页， Floyd算法 传递闭包
题目意思：
给出n个不等式，比较若干个大写字母的大小关系。然后确定这n个等式会得出以下3个结果：
1) n个字母的大小关系唯一确定， 此时输出第几条不等式就能得出全部大小和 这些大写字母从小到大的排列顺序的字符串；
2) 大小关系出现矛盾， 输出第几条不等式，就得出矛盾了；
3) 大小关系不能确定；
本题要点：
0、 如果 i < j, 用 d[i][j] == 1 表示；i > j 和 i 和 j的关系不确定，用 d[i][j] == 0表示；
Floyd 算法 刚好能传递每个字母的关系；
1、依次扫描不等式，在出现矛盾之前成功的，也算成功；
2、暴力计算，没读入一个不等式，就用 Floyd 算法计算一次当前的所有 字母的大小关系，
如果是矛盾或者刚好确定关系的，直接输出；
3、 当要从小到大输出所有的字母的时候，数组 d2[MaxN][MaxN] 的每一行相加，表示当前有多少个字母大于当前字母；
比如 第 2 行， d[2][1] + d[2][2] + … + d[2][n] 表示大于字母 B 的字母有多少个；
然后，清楚直到 B 具体排第几位
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 30;
int n, m;
int d1[MaxN][MaxN];
int d2[MaxN][MaxN];
char str[4] = {
0};int floyd() // 返回 -1 表示矛盾；0 表示不确定；1 表示确定
{
memcpy(d2, d1, sizeof(d1));for(int k = 1; k <= n; ++k)for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j){
d2[i][j] |= d2[i][k] & d2[k][j]; // i < k 并且 k < j, 可以推导出来 i < jif(d2[i][j] == d2[j][i] && d2[i][j] && i != j)// 矛盾{
return -1;}}for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j){
if (d2[i][j] == d2[j][i] && !d2[i][j] && i != j) {
return 0;}}return 1;
}void solve()
{
bool not_sure = true;memset(d1, 0, sizeof(d1));for(int k = 1; k <= m; ++k){
scanf("%s", str);d1[str[0] - 'A' + 1][str[2] - 'A' + 1] = 1;int now = floyd();if(not_sure){
if(-1 == now) //矛盾{
printf("Inconsistency found after %d relations.\n", k);not_sure = false;}else if(1 == now){
//确定//计算出这个关系确定的各个字母，用字符串连起来char ans[MaxN] = {
0};int s[MaxN] = {
0};for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
s[i] += d2[i][j]; }}for(int i = 1; i <= n; ++i){
ans[n - s[i] - 1] = 'A' + i - 1;}printf("Sorted sequence determined after %d relations: %s.\n", k, ans);not_sure = false;}}}if(not_sure){
printf("Sorted sequence cannot be determined.\n");}
}int main()
{
while(scanf("%d%d", &n, &m) != EOF && n){
solve();}return 0;
}/* 4 6 A<B A<C B<C C<D B<D A<B 3 2 A<B B<A 26 1 A<Z 0 0 *//* Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined. */