题目链接:2019 ECNU Campus Invitational Contest-I.Induced Metric Space
题意:
给一个距离矩阵,i行j列表示i点到j点的距离,判断求出该距离矩阵中的未知值,并判断该矩阵是否合法。
该矩阵满足:
- 每个点到自身的距离为0。
- 距离全部为非负数。
- dis(i,j)=dis(j,i)。
- dis(i,j)<=dis(i,k)+dis(k,j)。
矩阵中的未知值全部用-1表示。
题解:
先把矩阵中所有的-1设为inf(注意inf的大小,题面要求答案不超过1e9),然后对角补全,并判断该矩阵是否合法。第四点要求用Floyd判断即可,若存在点对(i,j,k)被松弛了,那么就不合法。
参考代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3fff;
const ll mod = 1e9 + 7;
ll mp[503][503], f[503][503];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
scanf("%lld", &mp[i][j]);
if (mp[i][j] == -1)
f[i][j] = inf;
else
f[i][j] = mp[i][j];
}
bool flag = 0;
for (int i = 1; i <= n; i++)
{
if (f[i][i] == inf || f[i][i] == 0)
f[i][i] = 0;
else
flag = 1;
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
if (f[i][j] == inf && f[j][i] == inf)
continue;
else
{
if (f[i][j] == inf || f[j][i] == inf)
f[i][j] = f[j][i] = min(f[i][j], f[j][i]);
else if (f[i][j] != f[j][i])
flag = 1;
}
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (mp[i][j] == -1 || i == j)
continue;
if (mp[i][j] != f[i][j] || f[i][j] != f[j][i])
flag = 1;
}
if (flag)
puts("NO");
else
{
puts("YES");
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
printf("%lld ", f[i][j]);
puts("");
}
}
}
return 0;
}