河南省第五届程序设计竞赛--Metric Matrice

我就是我 2022-08-26 00:47 167阅读 0赞

## Metric Matrice ##

时间限制：1000 ms  |  内存限制：65535 KB

难度：1

描述

Given as input a square distance matrix, where a\[i\]\[j\] is the distance between point i and point j, determine if the distance matrix is "a  metric" or not.

A distance matrix a\[i\]\[j\] is a metric if and only if

1.  a\[i\]\[i\] = 0

2, a\[i\]\[j\]> 0  if i != j

3.  a\[i\]\[j\] = a\[j\]\[i\]

4.  a\[i\]\[j\] + a\[j\]\[k\] >= a\[i\]\[k\]  i ¹ j ¹ k

输入

The first line of input gives a single integer, 1 ≤ N ≤ 5, the number of test cases. Then follow, for each test case,  
\* Line 1: One integer, N, the rows and number of columns, 2 <= N <= 30  
\* Line 2..N+1: N lines, each with N space-separated integers   
(-32000 <=each integer <= 32000).

输出

Output for each test case , a single line with a single digit, which is the lowest digit of the possible facts on this list:  
\* 0: The matrix is a metric  
\* 1: The matrix is not a metric, it violates rule 1 above  
\* 2: The matrix is not a metric, it violates rule 2 above  
\* 3: The matrix is not a metric, it violates rule 3 above  
\* 4: The matrix is not a metric, it violates rule 4 above

样例输入

0 1 2 3

1 0 1 2

2 1 0 1

3 2 1 0

0 3

2 0

0 1 4

1 0 1

4 1 0

样例输出

#include <iostream>
    #include <algorithm>
    
    using std::endl;
    using std::cout;
    using std::cin;
    using std::sort;
    
    int main()
    {
    	int K;
    	cin >> K;
    	//用数组来保存每个规则是否成立
    	
    	while(K--)
    	{
    		int flag[5] = {0};
    		int n;
    		cin >> n;
    		int data[30][30];
    		for(int i=0; i<n; ++i)
    			for(int j=0; j<n; ++j)
    			{
    				cin >> data[i][j];
    			}
    		for(int i=0; i<n; ++i)
    			for(int j=0; j<n; ++j)
    			{
    				//如果不满足规则1则flag=1
    				if(i==j && data[i][i] != 0)
    				{
    					flag[1] = 1;
    				}
    				//检查规则二
    				if(i != j && data[i][j] <= 0)
    				{
    					flag[2] = 2;
    				}
    				//如果不满足规则三
    				if(i !=j && data[i][j] != data[j][i])
    				{
    					flag[3] = 3;
    				}
    				if(i != j)
    				{
    					for(int s=0; s<n; ++s)
    					{
    						if(s != i && data[i][j] + data[j][s] < data[i][s])
    						{
    							flag[4] = 4;
    						}
    					}
    				}	
    			}
    		sort(flag+1, flag+5);
    		int cnt;
    		for( cnt=1 ; cnt<5; ++cnt)
    		{
    			if(flag[cnt] > 0)
    			{
    				cout << flag[cnt] << endl;
    				break;
    			}
    		}
    		if(cnt >= 5)
    			cout << flag[0] << endl;
    	}
    	system("pause");
    	return 0;
    }