[bitset/最小瓶颈生成树]CF632F Magic Matrix_综合

题意

给你一个 $n×nn\times n$ 的矩阵 $A$ ，你需要判断这个矩阵是否满足以下条件:

1. $Ai,j=Aj,i(1≤i,j≤n)A_{i,j}=A_{j,i}(1\leq i,j \leq n)$

2. $Ai,i=0(1≤i≤n)A_{i,i}=0(1\leq i \leq n)$

3. $?i,j,k\forall i,j,k$ 都有 $Ai,j≤max?(Ai,k,Aj,k)(1≤i,j,k≤n)A_{i,j}\leq \max(A_{i,k},A_{j,k})(1\leq i,j,k \leq n)$ ，注意这里的 $i, j, k$ 并不满足互不相同。

如果满足，输出MAGIC，否则输出NOT MAGIC。

子任务:(~~鼓励大家想正解~~)

对于全部测试点： $n≤2.5×103,ai,j≤109n\leq 2.5\times 10^3,a_{i,j}\leq 10^9$ 。

subtask1(1pts)： $n≤3n\leq 3$ 。

subtask2(1pts)： $\leq 100$ 。

subtask3(1pts)： $?i,j且i≠j\forall i,j且i≠j$ ，有 $a_{i,j}=C$ ， $C$ 为常数。

subtask4(97pts)：无特殊限制。

样例

MAGIC

NOT MAGIC

[没办法了，这图片上传的时候变小了…]
[bitset/最小瓶颈生成树]CF632F Magic Matrix

提示

1.合法矩阵显然是邻接矩阵形式，因此这其实可以转化为一个图论问题。

2.其实有一个subtask还是有用的。

3.对于满足条件的图中的任意一个三元组 $(a, b, c)$ ，它们之间两条权值最大的边一定相等。

4.在线学习一个[大概是没有学过的]生成树：

最小瓶颈生成树：
无向图 $G$ 的一颗瓶颈生成树是这样的一颗生成树，它最大的边权值在 $G$ 的所有生成树中是最小的。瓶颈生成树的值为 $T$ 中最大权值边的权。
显然最小生成树是一种特殊的最小瓶颈生成树。

算法一:bitset暴力优化

提示了这么多还是不会做?bitset!

我们的任务是要找是否存在 $Ai,j>max?(Ai,k,Aj,k)(1≤i,j,k≤n)A_{i,j}> \max(A_{i,k},A_{j,k})(1\leq i,j,k \leq n)$ ，如果存在就不合法。

很容易发现一个做法——我们从小到大加入 $A_{i,j},i,j)$ ，对于每个点我们维护二维数组 $G [i] [j]$ 表示现在 $i$ 与 $j$ 是否连边。

那么在加入 $i, j$ 时已经存在 $(i, k)$ , $(k, j)$ 的两条边就不合法了。
注意边权相同的，加入没有先后顺序，应该一起加。
直接暴力检查连边还是 $O(n^3)$ 。
但是 $G [i] [j]$ 是一个0/1数组，如果我们将第二维压成二进制的话，检查路径就是 $\& G[j])$ 。

因此我们用bitset维护第二维。
复杂度: $O(n3w)O(\frac{n^3}{w})$
实际测试时间只要2s左右，完全可以通过。

/*Lower_Rating*/
/*CF632F Magic Matrix bitset*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<bitset>
using namespace std;#define LL long long
#define MAXN 2500
#define MOD 998244353
#define Pr pair<LL,int>
#define X first
#define Y second
#define INF 1000000000000000000
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int x,int y){
    return (x+y>=MOD)?x+y-MOD:x+y;}
int dec(int x,int y){
    return (x-y<0)?x-y+MOD:x-y;}
int mul(int x,int y){
    return 1LL*x*y%MOD;}int n,ecnt;
int a[MAXN+5][MAXN+5];
struct edge{
    int u,v;
}e[MAXN*MAXN+5];
bool cmp(edge s1,edge s2){
    return a[s1.u][s1.v]<a[s2.u][s2.v];
}
bitset<MAXN> G[MAXN+5];
int main()
{
    n=read();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
    a[i][j]=read();e[++ecnt]=(edge){
    i,j};}sort(e+1,e+ecnt+1,cmp);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][j]!=a[j][i]){
    printf("NOT MAGIC\n");return 0;}for(int i=1;i<=n;i++)if(a[i][i]){
    printf("NOT MAGIC\n");return 0;}for(int i=1,j;i<=ecnt;i++){
    j=i;while(j<=ecnt&&a[e[i].u][e[i].v]==a[e[j].u][e[j].v])j++;for(int k=i;k<j;k++)if((G[e[k].u]&G[e[k].v]).any()){
    printf("NOT MAGIC\n");return 0;}for(int k=i;k<j;k++)G[e[k].u][e[k].v]=1;i=j;}printf("MAGIC\n");
}

证明1：探究问题的本质

我们可以检验每个 $i, j$ 是否满足 $Ai,j≤min?k=1n{max?(Ai,k,Aj,k)}(1≤i,j≤n)A_{i,j}\leq \min^{n}_{k=1}\{\max(A_{i,k},A_{j,k})\}(1\leq i,j \leq n)$ 。
我们设 $bi,j=min?k=1n{max?(Ai,k,Aj,k)}b_{i,j}=\min^{n}_{k=1}\{\max(A_{i,k},A_{j,k})\}$ 。
注意到当 $k = i$ 时， $b_{i,j}=max(A_{i,i},A_{i,j})=A_{i,j}$ 。
因此， $bi,j≤Ai,jb_{i,j}\leq A_{i,j}$ 。

发现了什么？其实 $b_{i,j}=A_{i,j}$ 。

易得 $b_{i,j}$ 的含义就是从 $i$ 到 $j$ 任意一条路径的最大边权的最小值。

证明2：从三元环到最小瓶颈生成树

我们先来分析最简单一种情况——三元环的性质。
根据提示3，我们可以发现：三元环的任意一个生成树的最大边权相等。
再根据提示4，最终得出：

三元环的任意一个生成树为最小瓶颈生成树。

而对于一完全图 $G$ ，它由若干个三元环组成。

对于每一个生成树，虽然有可能三元组 $(a, b, c)$ 之间只间接联通，但由证明一得出，环上的边权一定存在于这条联通路径上。

? 因此，我们证明了每个生成树都包含原来完全图 $G$ 的所有边权。

? 显然，我们的每颗生成树上的最大边权相等，因此，我们得出：

满足条件的完全图 $G$ 满足任意一个生成树为最小瓶颈生成树。并且，对于 $G$ 的任意一个子图 $G^{'}$ ，它的任意一个生成树也一定是一个最小瓶颈生成树。

算法二

有了上面两个结论之后就简单多了。

我们知道最小瓶颈生成树的特殊形态为最小生成树，因此，我们可以先找出原图的最小生成树。

根据证明2，可以得到，在从小到大加边的时候，加完相同的边时每个联通块一定是完全图。

因此维护 $siz_i$ (联通块点数)， $cnt_i$ (联通块边数)，加完相同的边暴力判完全图就是了(复杂度不变，这里略过)。

复杂度: $O(n^2)$ 或 $O(n^2 \log n)$ (看你用什么做生成树了)。

算法三

与算法二一样，先找出生成树。

基于证明1，对于不在生成树上的边 $(u, v)$ ，边权一定是最小生成树的路径上最大的，因此我们每次在 $(u, v)$ 路径上去掉一条边，变为 $(f a [u], v)$ ，只要边 $(f a [u], v)$ 合法，且满足 $wu,v≤max?(wfa[u],v,wu,fa[u])w_{u,v}\leq \max(w_{fa[u],v},w_{u,fa[u]})$ ，那么 $(u, v)$ 也一定合法。

? [实在是不想再写了…见谅…]

? 复杂度: $O(n^2)$ 或 $O(n^2 \log n)$ 。

后记

做这道题花了我非常多的时间。
因为网上的博客全都是直接给出最小生成树的结论，没有任何解释和证明。就连官方题解都是莫名其妙的就说可以用最小生成树做…自己想证明方法是在是太难受了啊…
所以如果有问题，请指出。