He began to dig up what his ancestors (ycx) had left behind jpg
Originally, I wanted to use a purple question of water as the 500th purple question of AC, but I found that a divine question was opened.
First of all, let's talk about a violent practice I think of. Condition 1 and condition 2 are directly scanned and judged. First, sort all points according to the weight size of \ (a {I, J} \) from small to large, and insert these points in turn. We maintain a bool array \ (VIS \), \ (VIS {I, J} \) of \ (n \ times, n \) in real time, which indicates whether the number in the \ (I \) row and \ (J \) column has been accessed. When we insert a \ (a {I, J} \), if \ (\ exist k\in[1,n] \) makes \ (VIS {I, K} = vis {J, K} = 1 \), it means that \ (a {I, K}, a {J, K} \) are less than \ (a {I, J} \), it does not meet condition 3. Replacing bool array with bitset can realize \ (\ mathcal O(\dfrac{n}{\omega}) \) judgment. Another small problem is that if there are duplicate weights, such as \ (a {I, J} = a {I ', J'} \), assuming that \ (a {I ', J'} \) is accessed after \ (a {I, J} \), when accessing \ (a {I ', J'} \), \ (VIS {I, J} \) is already equal to \ (1 \). If in this case \ (i'=i \) and \ (VIS {J', J} \) is just equal to \ (1 \), the program will think that this situation does not meet condition 3, and in fact \ (\ max (a {I, j}, a {J ', J}) = a_{i',j'}\). This problem is also extremely easy to solve. Directly scan the numbers with the same weight through two pointers. For these numbers, judge them together and then insert them together.
Time complexity \ (\ dfrac{n^3}{\omega} \), ranking as the worst solution.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
x=0;char c=getchar();T neg=1;
while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=neg;
}
const int MAXN=2500;
int n,a[MAXN+5][MAXN+5];pair<int,pii> p[MAXN*MAXN+5];
bitset<MAXN+5> bt[MAXN+5];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);p[(i-1)*n+j]=mp(a[i][j],mp(i,j));
} sort(p+1,p+n*n+1);
for(int i=1;i<=n;i++) if(a[i][i]) return printf("NOT MAGIC\n"),0;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]!=a[j][i])
return printf("NOT MAGIC\n"),0;
for(int l=1,r=1;l<=n*n;l=r){
while(p[r].fi==p[l].fi&&r<=n*n){
int x=p[r].se.fi,y=p[r].se.se;
if((bt[x]&bt[y]).count()) return printf("NOT MAGIC\n"),0;
r++;
} for(int i=l;i<r;i++){int x=p[i].se.fi,y=p[i].se.se;bt[x][y]=1;}
} printf("MAGIC\n");
return 0;
}
In fact, we find that this thing is very closely related to graph theory. If we regard this matrix as an adjacency matrix, condition 1 means that there is no self ring in the graph, and condition 2 means \ (w {u, V} = w {V, u} \), that is, the matrix satisfying condition 1 and condition 2 is the adjacency matrix of an undirected weighted complete graph. Let's analyze condition 3 again. For example, there are four points \ (i,j,k,l \), according to condition three \ (w {I, K} \ Leq \ max (w {I, J}, w {J, K}), W_ {i,l}\leq\max(w_{i,k},w_{k,l})\leq\max\{w_{i,j},w_ {j,k},w_ {K, l} \} \), which means \ (\ forall, I, J \ in [1, n] \), the maximum value of edge weight on any \ (I, J \) path \ (\ GEQ, w#i{i, J} \). Therefore, the minimum value of the maximum weight on the path between \ (\ forall, I, J \ in [1, n] \), \ (I, J \) \ (\ GEQ w#uq{i, J} \). Seeing this condition, it is easy to think of the minimum bottleneck path - build the minimum spanning tree, so the minimum value of the maximum weight on the path between \ (I, J \) is the maximum value of the weight on the path of \ (I, J \) on the minimum spanning tree. So find the minimum spanning tree once, and then perform DFS for each point to find the maximum value of the weight on the path from it to each point. Note that this graph is a dense graph, \ (m=n^2 \), so the Prim of Kruskal and heap optimization is \ (m\log n=n^2\log n \), while the Prim without heap optimization is \ (n^2 \), so the efficiency of using Prim in this problem is higher.
However, this is the second time I wrote Prim (the first time was two years ago)... I'm used to Kruskal and I forget how Prim wrote
code(Kruskal):
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
x=0;char c=getchar();T neg=1;
while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=neg;
}
const int MAXN=2500;
int n,a[MAXN+5][MAXN+5],f[MAXN+5];
pair<int,pii> p[MAXN*MAXN+5];
int find(int x){return (!f[x])?x:f[x]=find(f[x]);}
bool merge(int x,int y){
x=find(x);y=find(y);
if(x!=y) return f[x]=y,1;
return 0;
}
int hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
void dfs(int x,int rt,int f,int mx){
if(f&&a[x][rt]>mx){printf("NOT MAGIC\n");exit(0);}
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(y==f) continue;
dfs(y,rt,x,max(mx,a[x][y]));
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);p[(i-1)*n+j]=mp(a[i][j],mp(i,j));
}
for(int i=1;i<=n;i++) if(a[i][i]) return printf("NOT MAGIC\n"),0;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]!=a[j][i])
return printf("NOT MAGIC\n"),0;
sort(p+1,p+n*n+1);
for(int i=1;i<=n*n;i++) if(merge(p[i].se.fi,p[i].se.se))
adde(p[i].se.fi,p[i].se.se),adde(p[i].se.se,p[i].se.fi);
for(int i=1;i<=n;i++) dfs(i,i,0,-1);
printf("MAGIC\n");
return 0;
}
code(Prim):
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
x=0;char c=getchar();T neg=1;
while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=neg;
}
const int MAXN=2500;
const int INF=0x3f3f3f3f;
int n,a[MAXN+5][MAXN+5],hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int mn[MAXN+5],fa[MAXN+5];bool vis[MAXN+5];
void prim(){
vis[1]=1;for(int i=2;i<=n;i++) mn[i]=a[1][i],fa[i]=1;
for(int i=1;i<=n-1;i++){
int mnv=INF,k=0;
for(int j=1;j<=n;j++) if(!vis[j]&&mn[j]<mnv) mnv=mn[j],k=j;
vis[k]=1;
for(int j=1;j<=n;j++) if(!vis[j]&&mn[j]>a[k][j]) mn[j]=a[k][j],fa[j]=k;
}
}
void dfs(int x,int rt,int f,int mx){
if(f&&a[x][rt]>mx){printf("NOT MAGIC\n");exit(0);}
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(y==f) continue;
dfs(y,rt,x,max(mx,a[x][y]));
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++) if(a[i][i]) return printf("NOT MAGIC\n"),0;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]!=a[j][i])
return printf("NOT MAGIC\n"),0;
prim();for(int i=2;i<=n;i++) adde(i,fa[i]),adde(fa[i],i);
for(int i=1;i<=n;i++) dfs(i,i,0,-1);printf("MAGIC\n");
return 0;
}
(good afternoon, Kruskal)