CF632F Magic Matrix 题解

题意：

定义一个大小为 $n\times n$ 矩阵 $a$ 为魔法矩阵，当且仅当 $a$ 满足以下条件：

以下 $i,j,k\in \mathbb{Z_+}$

$\forall i\in[1,n],~a_{i,i}=0$

$\forall i,j\in[1,n],~a_{i,j}=a_{j,i}$

$\forall i,j,k\in[1,n],~a_{i,j}\le\max\{a_{i,k},a_{j,k}\}$

给你一个矩阵，问它是不是魔法矩阵。

如果 $a$ 是魔法矩阵输出 $\texttt{MAGIC}$，否则输出 $\texttt{NOT MAGIC}$ 。

数据范围：

$1\leq n\leq 2500,~\forall i,j\in[1,n],~0\le a_{i,j}\le 10^9$

前两条限制已经告诉你了，这个东西就是个无向简单图的邻接矩阵，不然肯定不满足条件。

考虑第三条限制怎么处理。注意到后面的 $a_{i,k}$ 同样满足这样的性质，则

$a_{i,j} \le \max\left\{ { a_{i,k},~a_{k,j} } \right\} \le \max\left\{ { a_{i,k_1},~a_{k_1,k_2},~a_{k_2,j} } \right\} \le \dots \le \max\left\{ { a_{ i,k_1 }, ~ a_{k_1,k_2},~\cdots,~a_{k_{n-1},k_n},~a_{k_n,j} } \right\}$

称一条起点为 $i$ ，终点为 $j$ 的路径的权值为「其经过的边的边权的最大值」，记为 $d_{i,j}$ 。

则限制转化为

$\forall i,j \in [1,n],~a_{i,j} \le d_{i,j}$

而 $i\rightarrow j$ 也是一条合法的路径，故 $d_{i,j} \le a_{i,j}$

因此如果满足限制，则有

$\forall i,j \in [1,n],~a_{i,j} = d_{i,j}$

考虑如何求出 $d_{i,j}$ 。

不妨从每一条边的角度出发，观察它是怎么构成路径的权值的。

我们把所有边按从小到大的顺序依次添加，每次合并边两端点所在的连通块（如果已经连通就跳过）

不难发现其实这个过程就是建立了一棵最小生成树，且任意两点在树上的简单路径的权值就是他们的 $d_{i,j}$

时间复杂度 $O(m \log m)$ ，懒得写 $\mathtt{Prim}$ 。

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define debug (cout << "1145141919810...")
#define N ((int)(2500+15))
#define M ((int)(6250000+15))

int n,m,pos=1,head[N],f[N],sz[N],d[N],a[N][N];
struct Edge{int u,v,w,next;} e1[M],e2[N*2];
void init(int n){for(int i=1; i<=n; i++) f[i]=i, sz[i]=1;}
int find(int x){return f[x] == x ? x : f[x] = find(f[x]);}
void merge(int u,int v)
{
    int x=find(u), y=find(v);
    if(sz[x] > sz[y]) swap(x,y);
    f[x] = y; sz[y] += sz[x];
}
void addEdge(int u,int v,int w)
{
    e2[++pos]={u,v,w,head[u]};
    head[u] = pos;
}
void kruskal()
{
    int cnt=0; init(n);
    sort(e1+1,e1+1+m,[](Edge a,Edge b){return a.w < b.w;});
    for(int i=1; i<=m; i++)
    {
        int u=e1[i].u, v=e1[i].v, w=e1[i].w;
        if(find(u) != find(v))
        {
            merge(u,v);
            addEdge(u,v,w); addEdge(v,u,w);
            if(++cnt == n-1) return;
        }
    }
}
void dfs(int u,int fa)
{
    for(int i=head[u]; i; i=e2[i].next)
    {
        int v=e2[i].v; if(v == fa) continue;
        d[v] = max(d[u], e2[i].w); dfs(v,u);
    }
}
void ck(int x) {if(!x){cout << "NOT MAGIC\n",0; exit(0);}}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin >> a[i][j];
    for(int i=1; i<=n; i++) ck(!a[i][i]);
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            ck(a[i][j] == a[j][i]), e1[++m] = {i,j,a[i][j]};
    kruskal();
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) d[j]=0;
        dfs(i,i);
        for(int j=1; j<=n; j++) ck(a[i][j] == d[j]);
    }
    cout << "MAGIC" << '\n';
    return 0;
}