**弗洛伊德演算法
核心代碼
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，表示測驗資料的組數，
每組輸入首先是一個正整數m（m<=100），表示給定元素關系的個數，
接下來m行，每行一個元素關系，格式為：
元素1<元素2 或者 元素1>元素2
元素用一個大寫字母表示，輸入中不會包含沖突的關系，
輸出
對于每組輸入，第一行輸出“Case d:”，d是測驗資料的序號，從1開始，
接下來輸出所有推斷出的新的元素關系，按照字典序從小到大排序，格式為：
元素1<元素2
每個元素關系占一行，輸入中給定的元素關系不要輸出，
如果沒有新的元素關系推斷出來，則輸出NONE，
樣例輸入
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 <iostream>
#include<cmath>
#include<algorithm>
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://www.uj5u.com/qita/260134.html
標籤：其他
上一篇：云計算專業防火墻混合模式應用實驗