NYOJ 545-Metric Matrice【模拟】

谁借莪１个温暖的怀抱￠ 2022-07-26 05:19 13阅读 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

样例输入

240 1 2 31 0 1 22 1 0 13 2 1 020 32 0

样例输出

来源

[第五届河南省程序设计大赛][Link 1]

解题思路：

直接模拟。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int num[30][30];
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		int i,j;
    		int n;
    		scanf("%d",&n);
    		for(i=0;i<n;i++)
    		{
    			for(j=0;j<n;j++)
    			{
    				scanf("%d",&num[i][j]);
    			}
    		}
    		int m=1;
    		for(i=0;i<n;i++)
    		{
    			if(num[i][i]!=0)
    			{
    				printf("1\n");
    				m=0;
    				break;
    			}
    		}
    		if(m==0)
    		continue;
    		for(i=0;i<n;i++)
    		{
    			if(m==0)
    			break;
    			for(j=0;j<n;j++)
    			{
    				if(i!=j&&num[i][j]<=0)
    				{
    					m=0;
    					printf("2\n");
    					break;
    				}
    			}
    		}
    		if(m==0)
    		continue;
    		for(i=0;i<n;i++)
    		{
    			if(m==0)
    			break;
    			for(j=0;j<n;j++)
    			{
    				if((i!=j)&&(num[i][j]!=num[j][i])) 
    				{
    					printf("3\n");
    					m=0;
    					break;
    				}
    			}
    		}
    		if(m==0)
    		{
    			continue;
    		}
    		for(i=0;i<n;i++)
    		{
    			if(m==0)
    			break;
    			for(j=0;j<n;j++)
    			{
    				if(m==0)
    				break;
    				for(int k=0;k<n;k++)
    				{
    					if((i!=j)&&(i!=k)&&(j!=k)&&(num[i][j]+num[j][k]<num[i][k]))
    					{
    						printf("4\n");
    						m=0;
    						break;
    					}
    				}
    			}
    		}
    		if(m==0)
    		continue;
    		printf("0\n");
    	}
    	return 0;
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E7%AC%AC%E4%BA%94%E5%B1%8A%E6%B2%B3%E5%8D%97%E7%9C%81%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E5%A4%A7%E8%B5%9B