原题
CF472D Design Tutorial: Inverse the Problem
思路概述
题意分析
给定一个 \(n\) 点无向图的两两点对之间距离，即经过最短路算法后的邻接矩阵，要求判断原图是否为一个树。
思路简述
首先回到最短路算法最为关键的松弛操作，以 \(n\) 点图中的Floyd-Warshall算法为例，其核心部分的操作可以表达为：
\[dis_{i,j}=\min\{dis_{i,k}+dis_{k,j}\},1≤k≤n\text{且}k≠i,j \]由此可知，对于最短路算法后的一个邻接矩阵，其中任意没有连边的两点的距离必然是通过借助其他点进行松弛操作得到。
又根据树的特殊性质可知，若原图为树形结构，则其中存在连边的两点在最短路操作中不会被松弛，即对于最后的邻接矩阵中的每个点而言，与其距离最小的点必然是与其有连边点。因此，本题的突破口即为邻接矩阵中距离最小的点对。
由于是讨论距离最小的点对，则可以引入最小生成树（此处笔者选择用比较顺手的Kruskal）。把邻接矩阵中所有点的距离都看作边，即得到一个完全图。开一个空图来保存加入的边，用于复原原图（下文称其为复原图）。然后把图中所有边升序排序后，每次选取最小的边判定两端点是否联通，若联通图，就在复原图中加上该边，然后重复以上操作，直到整个图完全连通。
最后通过最短路算法在复原图中验证树形结构的存在性。若最短路得到的结果与给出的邻接矩阵不符，则说明原图必然存在环，不满足树形结构的条件。
算法实现
关于邻接矩阵读入
由样例可见，本题读入的邻接矩阵存在十万甚至九万条奇葩数据，包括但不限于自己到自己距离为 \(1\) 的点和权值为 \(0\) 的边。
因此，在读入时就要注意处理这些数据对算法的干扰。
关于验证
最短路可以跑加堆优化的Dijkstra。
但是考虑到本题相当一部分数据是可以形成树的，所以可以考虑直接DFS，在树上的时间复杂度比跑其他最短路算法更快，而且实现更简单。
AC code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<set>
#include<ctime>
#define RI register int
#define RB register bool
using namespace std;
const int maxn=2e3+10;
typedef struct
{
int pre,dep;
}node;
typedef struct
{
int u,v,w;
}side;
typedef struct
{
int u,w,nex;
}graph;
node e[maxn];
side s[maxn*maxn];
graph g[maxn*maxn];
int n,m,cnt,rec;
int fir[maxn],gph[maxn][maxn];
bool jdg=1;
bool v[maxn];
inline bool cmp(side x,side y);
inline void init(int lim);
inline int find(int x);
inline void merge(int x,int y);
inline void add(int x,int y,int w);
inline void dfs(int st,int x,int sp);
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;init(n);
for(RI i=1,x;i<=n;++i)
for(RI j=1;j<=n;++j)
{
cin >> x;gph[i][j]=x;
if(i!=j && x) s[++m]=(side){i,j,x};
}
sort(s+1,s+m+1,cmp);
for(RI i=1;i<=m;++i)
if(find(s[i].u)!=find(s[i].v))
{
add(s[i].u,s[i].v,s[i].w);
merge(s[i].u,s[i].v);
}
for(RI i=1;i<=n;++i)
{
memset(v,0,sizeof(v));rec=0;
dfs(i,i,0);
}
if(jdg && rec==n) puts("YES");
else puts("NO");
return 0;
}
inline bool cmp(side x,side y)
{
return x.w<y.w;
}
inline void init(int lim)
{
for(RI i=1;i<=lim;++i) e[i]=(node){i,1};
return;
}
inline int find(int x)
{
return (e[x].pre==x)?x:(e[x].pre=find(e[x].pre));
}
inline void merge(int x,int y)
{
RI fx=find(x),fy=find(y);
if(e[fx].dep<=e[fy].dep) e[fx].pre=fy;
else e[fy].pre=fx;
if(e[fx].dep==e[fy].dep && fx!=fy) ++e[fy].dep;
return;
}
inline void dfs(int st,int x,int sp)
{
if(!v[x])
{
v[x]=1;++rec;
if(sp!=gph[st][x]) jdg=0;
for(RI i=fir[x];i;i=g[i].nex)
dfs(st,g[i].u,sp+g[i].w);
}
return;
}
inline void add(int x,int y,int w)
{
g[++cnt]=(graph){y,w,fir[x]};fir[x]=cnt;
g[++cnt]=(graph){x,w,fir[y]};fir[y]=cnt;
return;
}