题目链接  

考虑第三个条件，如果不符合的话说明$a[i][k] < a[i][j]$ 或 $a[j][k] < a[i][j]$

于是我们把所有的$(a[i][j], i, j)$升序排序，然后检查当前的三元组$(a[i][j], i, j)$的时候，

先确保第一维值小于他的所有三元组$(x, y, z)$中$f[y][z]$已经设置成$1$

然后看$f[i]$和$f[j]$是否有交集，如果有则说明不符合题意。

#include 
     
      using namespace std;#define rep(i, a, b)	for (int i(a); i <= (b); ++i)#define dec(i, a, b)	for (int i(a); i >= (b); --i)#define MP		make_pair#define fi		first#define se		secondtypedef pair 
      
        > PII;const int N = 2510;int a[N][N];int cnt, now;int n;PII c[N * N];bitset 
       
         f[N], tmp;int main(){	scanf("%d", &n);	rep(i, 1, n) rep(j, 1, n) scanf("%d", a[i] + j);		rep(i, 1, n - 1) rep(j, i + 1, n) if (a[i][j] ^ a[j][i]) return 0 * puts("NOT MAGIC");	rep(i, 1, n) if (a[i][i]) return 0 * puts("NOT MAGIC");	rep(i, 1, n) rep(j, 1, n) c[++cnt] = MP(a[i][j], MP(i, j));	sort(c + 1, c + cnt + 1);	now = 1;	rep(i, 1, cnt){		for (; now < i && c[now].fi < c[i].fi; ){			f[c[now].se.fi][c[now].se.se] = 1;			f[c[now].se.se][c[now].se.fi] = 1;			++now;		}		tmp = f[c[i].se.fi] & f[c[i].se.se];		if (tmp.any()) return 0 * puts("NOT MAGIC");	}	return 0 * puts("MAGIC");}