Magic Matrix(CF632 F)(bitset,最小生成树)

题目

思路

我们可以看成是 $n^2$ 个点的完全图
发现对于三个点：

可以得到
$$?\begin{array}{l}a\ge max(b,c)\\ b\ge max(a,c)\\ c\ge max(a,b)\end{array}$$
设 $a\ge b\ge c$
可以得到 $a=b$
于是对于所有三元环而言最大值等于次大值

方法一(bitset)

我们可以从大到小加入边
假设现在加入 $(i,j)$ 如果已经存在 $(i,k),(k,j)$ 就不行了
注意边权相同的一起判断，不要一个一个加
这是 $O(n^3)$ 的
但可以用 $bitset$ 来优化 $n^3$ 暴力
我们可以看作检查 $(i,k),(j,k)$
我们只需要 $G[i][j]$ 表示 $(i,j)$ 是否连边
就判断 KaTeX parse error: Expected 'EOF', got '&' at position 5: G[i]&?G[j] 即可
时间复杂度 $O(\frac{n^3}{64})$

方法二(最小生成树)

考虑加边时候必定是完全图考虑如果不是完全图：

找到一条即将加入的一条图中没有的边 $(i,j)$ ，必然存在 $(i,k),(k,j)$ 的边，否则不连通
于是此时边的权值大于 $(i,k),(k,j)$ 并不满足三元环最大值等于次大值的条件
注意边权相同的一起判断，不要一个一个加
实现用 $Prim$ 和 $Kruskal$ 均可
时间复杂度 $O(n^2)$ $O(n^{2}logn)$

代码

代码一

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define MAXN 2500
#define INF 0x3f3f3f3f
bitset<MAXN+5> G[MAXN+5];
struct Edge{
    int u,v,w;friend bool operator < (Edge a,Edge b){
    return a.w<b.w;}
}edge[MAXN*MAXN+5];
int main(){
    int n=read();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)edge[(i-1)*n+j]=(Edge){
    i,j,read()};for(int i=1;i<=n;i++)if(edge[(i-1)*n+i].w!=0){
    puts("NOT MAGIC");return 0;}for(int i=1;i<=n;i++)for(int j=1;j<i;j++)if(edge[(i-1)*n+j].w!=edge[(j-1)*n+i].w){
    puts("NOT MAGIC");return 0;}sort(edge+1,edge+n*n+1);for(int i=1;i<=n*n;){
    int j=i;while(j<n*n&&edge[j+1].w==edge[i].w) j++;for(int t=i;t<=j;t++){
    int u=edge[t].u,v=edge[t].v;if(u==v) continue;if((G[u]&G[v]).count()>=1){
    puts("NOT MAGIC");return 0;}}for(int t=i;t<=j;t++){
    if(edge[t].u==edge[t].v) continue;G[edge[t].u][edge[t].v]=1;}i=j+1;}puts("MAGIC");return 0;
}

代码二

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define MAXN 2500
#define INF 0x3f3f3f3f
struct Edge{
    int u,v,w;friend bool operator < (Edge a,Edge b){
    return a.w<b.w;}
}edge[MAXN*MAXN+5];
int fa[MAXN*MAXN+5];
int Find(int x){
    return fa[x]==x?x:(fa[x]=Find(fa[x]));}
int main(){
    int n=read();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)edge[(i-1)*n+j]=(Edge){
    i,j,read()},fa[(i-1)*n+j]=(i-1)*n+j;for(int i=1;i<=n;i++)if(edge[(i-1)*n+i].w!=0){
    puts("NOT MAGIC");return 0;}for(int i=1;i<=n;i++)for(int j=1;j<i;j++)if(edge[(i-1)*n+j].w!=edge[(j-1)*n+i].w){
    puts("NOT MAGIC");return 0;}sort(edge+1,edge+n*n+1);for(int i=1;i<=n*n;){
    int j=i;while(j<n*n&&edge[j+1].w==edge[i].w) j++;for(int t=i;t<=j;t++){
    int fu=Find(edge[t].u),fv=Find(edge[t].v);if(edge[t].u==edge[t].v) continue;if(fu==fv){
    puts("NOT MAGIC");return 0;}}for(int t=i;t<=j;t++){
    int fu=Find(edge[t].u),fv=Find(edge[t].v);if(fu!=fv) fa[fv]=fu;}i=j+1;}puts("MAGIC");return 0;
}

思考

对于问题如果能转化为快速求交考虑 $bitset$
这道题推出三元环和连通时是完全图的特点非常巧妙