本文共 1748 字，大约阅读时间需要 5 分钟。

**弗洛伊德算法

核心代码

1     for(k=1;k<=n;k++)  2     for(i=1;i<=n;i++)  3     for(j=1;j<=n;j++)  4     if(e[i][j]>e[i][k]+e[k][j])  5                      e[i][j]=e[i][k]+e[k][j];

P1068:关系推断：

描述

给你一些已经确定的元素之间的关系，请你判断是否能从这些元素关系中推断出其他的元素关系。

输入

输入的第一行是一个整数N，表示测试数据的组数。

输出

对于每组输入，第一行输出“Case d:”，d是测试数据的序号，从1开始。

样例输入

2

3

A<B

C>B

C<D

2

A<B

C<D

样例输出

Case 1:

A<C

A<D

B<D

Case 2:

NONE

HINT

弗洛伊德算法

#include 
   
    #include
    
     #include
     
      using namespace std;int main(){
   	int n;	cin >> n;	for (int i = 1; i <= n; i++)	{
   		int m;		cin >> m;		int a[26][26];		for (int i = 0; i < 26; i++)		{
   			for (int j = 0; j < 26; j++)			{
   				if (i == j)				{
   					a[i][j] = 0;				}				else a[i][j] = 99;			}		}		int max1 = 0;		for (int i = 0; i < m; i++)		{
   			string b;			cin >> b;			if (b[1] == '<')			{
   				a[int(b[2]) - 65][int(b[0]) - 65] = 1;			}			else if (b[1] == '>')			{
   				a[int(b[0]) - 65][int(b[2]) - 65] = 1;			}			max1 = max(max(int(b[2]) - 65, int(b[0]) - 65), max1);		}		for (int k = 0; k <= max1; k++)		{
   			for (int i = 0; i <= max1; i++)			{
   				for (int j = 0; j <= max1; j++)				{
   					if (a[i][j] > a[i][k] + a[k][j])					{
   						a[i][j] = a[i][k] + a[k][j];					}				}			}		}		cout << "Case " << i <<":"<< endl;		int cnt = 0;		for (int j = 0; j <= max1; j++)//按字典序输出		{
   			for (int i = 0; i <= max1; i++)			{
   				if (a[i][j] != 99 && a[i][j] != 0 && a[i][j] != 1)				{
   					cnt++;					cout << char(j + 65) << "<" << char(i + 65) << endl;				}			}		}		if (cnt == 0)		{
   			cout << "NONE" << endl;		}	}}
     
    
   

转载地址：https://blog.csdn.net/YYDS777/article/details/113819183 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！