题目概述

有 $n\times n$ 的矩阵 $a$ ，判断该矩阵是否满足：1. $a_{i,j}=a_{j,i}$ 。2. $a_{i,i}=0$ 。3. $\forall i,j,k,a_{i,j}\le max\{a_{i,k},a_{j,k}\}$ 。

解题报告

神仙题……我们观察第三个式子，会发现这和最小生成树长得很像……

把 $a_{j,k}$ 代成 $max\{a_{j,t},a_{k,t}\}$ ，那么 $a_{i,j}\le max\{a_{i,k},a_{k,t},a_{j,t}\}$ ，然后将 $a_{j,t}$ 又代成 $a_{j,u}$ ……

这样最终可以代成：$a_{i,j}\le max\{a_{i,k_1},a_{k_1,k_2},a_{k_2,k_3},\cdots,a_{k_m,j}\}​$ ，其中 $\{k_m\}​$ 是一个序列，可以认为是一段路径！

也就是说，令 $f_{i,j}$ 表示最小生成树中 $(i,j)$ 路径上的最大值，那么 $\forall i,j,a_{i,j}\le f_{i,j}​$ 。

又因为 $f_{i,j}$ 其实也表示 $(i,j)$ 所有路径中最长边权的最小值，所以 $a_{i,j}\ge f_{i,j}$（否则 $f_{i,j}$ 可以直接给 $a_{i,j}$ ）。

根据上面两个条件，就可以得到 $a_{i,j}=f_{i,j}$ ，所以只需要求出最小生成树，并求出 $f_{i,j}$ 即可。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=2500;

int n,a[maxn+5][maxn+5],cst[maxn+5],ID[maxn+5],b[maxn+5][maxn+5];bool vis[maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],w[(maxn<<1)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int st,int x,int pre=0,int MAX=0){
    for (int j=(b[st][x]=MAX,lnk[x]);j;j=nxt[j])
        if (son[j]!=pre) Dfs(st,son[j],x,max(MAX,w[j]));
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) readi(a[i][j]);
    for (int i=1;i<=n;i++) if (a[i][i]) return puts("NOT MAGIC"),0;
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (a[i][j]!=a[j][i]) return puts("NOT MAGIC"),0;
    for (int i=1;i<=n;i++) cst[i]=a[1][i],ID[i]=1;vis[1]=true;
    for (int i=1;i<n;i++){
        int k=-1,MIN=2e9;for (int j=1;j<=n;j++) if (!vis[j]&&cst[j]<MIN) MIN=cst[k=j];
        vis[k]=true;for (int j=1;j<=n;j++) if (!vis[j]&&a[k][j]<cst[j]) cst[j]=a[k][j],ID[j]=k;
    }for (int i=2;i<=n;i++) Add(ID[i],i,cst[i]),Add(i,ID[i],cst[i]);
    for (int i=1;i<=n;i++) Dfs(i,i);
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (a[i][j]!=b[i][j]) return puts("NOT MAGIC"),0;
    puts("MAGIC");return 0;
}