第五届河南省程序设计大赛——F Metric Matrice

柔光的暖阳◎ 2022-02-12 15:37 276阅读 0赞

## 题目描述: ##

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

## 输入描述: ##

<span style="color:#000000">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).</span>

## 输出描述: ##

<span style="color:#000000">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
    </span>

## 样例输入: ##

复制

2
    4
    0 1 2 3
    1 0 1 2
    2 1 0 1
    3 2 1 0
    2
    0 3
    2 0

## 样例输出: ##

0
    3

有四种错误，如果矩阵符合某种错误就输出几，如果符合多种错误就输出更小的

ac代码：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<string>
    #include<map>
    #include<set>
    using namespace std;
    int main()
    {
    	int n,t,book[33][33],flag;
    	cin>>t;
    	while(t--){
    		flag=0;
    		cin>>n;
    		for(int i=0;i<n;i++){
    			for(int j=0;j<n;j++){
    				cin>>book[i][j];
    			}
    		}
    		for(int i=0;i<n;i++){
    			for(int j=0;j<n;j++){
    				if(book[i][j]<=0&&i!=j){  //错误2的情况， 
    					flag=2;
    					cout<<flag<<endl;
    					break;
    				}
    				if(book[i][j]!=book[j][i]&&book[j][i]>0){  //错误3的情况，但是对调角也如果符合错误2，则跳过， 
    					flag=3;
    					cout<<flag<<endl;
    					break;
    				}if(book[i][j]!=0&&i==j){  //错误1的情况 
    				    flag=1;
    				    cout<<flag<<endl;
    				    break;
    			    }
    			}
    			if(flag)break;
    		}
    		if(flag)continue;
    		for(int i=0;i<n;i++){    //错误4的情况 
    			for(int j=0;j<n;j++){
    				for(int k=0;k<n;k++){
    					if(k==i||i==j||j==k)continue;
    					if(book[i][j]>book[i][k]+book[k][j]){
    						flag=4;
    						cout<<flag<<endl;
    						break;
    					}
    				}
    				if(flag)break;
    			}
    			if(flag)break;
    		}
    		if(flag)continue;
    		cout<<flag<<endl;  //若所有错误都没有，输出0 
    	}
    	return 0;
    }