2019 ECNU Campus Invitational Contest I. Induced Metric Space

发表于 |
字数统计: 565 | 阅读时长 ≈ 3

题意

给定一个$n \times n$的矩阵A, $A_{i,j}$表示第$i$个点和第$j$个点之间的距离。同时有一些点的初始距离一开始不确定。

需要满以下几个条件
• the distance from a point to itself is zero,
• the distance between two distinct points is non-negative,
• the distance from A to B is the same as the distance from B to A, and
• the distance from A to B (directly) is less than or equal to the distance from A to B via any third point C, i.e., $d(A, B) ≤ d(A, C) + d(C, B)$.
问是否可以做到，如果可以，构造出这样一个矩阵出来

解法

将-1的点置为inf，然后跑一遍floyd。
最后check

  1. 自己和自己的距离是否为0
  2. $i$到$j$的距离是否等于$j$到$i$的距离
  3. 原始的点的距离是否被改变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define mp make_pair
#define eps 1e-6
#define mo %= MOD
using namespace std;
const int maxn = 2e3 + 10;
const int MOD = 1e9 + 7;
const int inf = 0x3f3f3ff;
int g[maxn][maxn];
int dis[maxn][maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int cas;
    cin >> cas;
    while(cas--)
    {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
            {
                cin >> g[i][j];
                if(g[i][j] == -1)
                    dis[i][j] = inf;
                else
                    dis[i][j] = g[i][j];
            }
        bool flag = true;
        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++)
            {
                if(dis[i][j] == inf && dis[j][i] == inf)
                    continue;
                else
                {
                    if(dis[i][j] == inf || dis[j][i] == inf)
                        dis[i][j] = dis[j][i] = min(dis[i][j], dis[j][i]);
                    else if(dis[i][j] != dis[j][i])
                        flag = false;
                }
            }
        for(int i = 0; i < n; i++)
        {
            if(dis[i][i] != 0)
            {
                if(dis[i][i] == inf)
                    dis[i][i] = 0;
                else
                    flag = false;
            }
        }
        if(!flag)
        {
            cout << "NO" << endl;
            continue;
        }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                for(int k = 0; k < n; k++)
                    dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
            {
                if(g[i][j] == -1 || i == j)
                    continue;
                if(g[i][j] != dis[i][j] || dis[i][j] != dis[j][i])
                    flag = false;
            }
        if(!flag)
        {
            cout << "NO" << endl;
            continue;
        }
        else
        {
            cout << "YES" << endl;
            for(int i = 0; i < n; i++, cout << endl)
                for(int j = 0; j < n; j++)
                    cout << dis[i][j] << ' ';
        }
    }
    return 0;
}