题解 CF632F 【Magic Matrix】

暴力

当看到$n≤2500$和5000ms/512MB的时空限制时,

我就想到 开花 暴力(看到iki9奆佬的暴力之后,我深深地感受到了我是多么地菜)

这道题的暴力其实比较好打,按着题意打就可以了,

我的是 $ O(n^3) $ 暴力,所以我的暴力这道题并过不去,那我打出来干什么呢?仅供欣赏,不做讲解(同样打 $ O(n^3) $ 暴力的同学可以去这里交一下,题目有一点小魔改,需要改一下程序的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

const int FFF=2500+5;

int n;
int a[FFF][FFF];

int main()
{
ios::sync_with_stdio(false);
scanf("%d",&n);
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
scanf("%d",&a[i][j]);
}
}
for(int i=0;i<n;++i)
{
if(a[i][i]!=0)
{
puts("NOT MAGIC");
return 0;
}
}
for(int i=0;i<n;++i)
{
for(int j=0;j<i+1;++j)
{
if(i!=j)
{
if(a[i][j]!=a[j][i])
{
puts("NOT MAGIC");
return 0;
}
}
}
}
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
if(i!=j)
{
for(int k=0;k<n;++k)
{
if(a[i][j]>max(a[i][k],a[k][j]))
{
puts("NOT MAGIC");
return 0;
}
}
}
}
}
puts("MAGIC");
return 0;
}

应该是正解

我们看一下本题的三个条件

  1. 对于每一个$i,j,a_{i,j}=a_{j,i}$(在矩阵中就是左下角的数和右上角的数对称相等)
  2. 对于每一个$i,a_{i,i}=0$(在矩阵中就是对角线都为 0)
  3. 对于每一个$i,j,k,a_{i,j}≥max(a_{i,k},a_{k,j})$(在矩阵中就是对于任意一个格子$(i,j)$要满足对于任意的 $k$,$a_{i,j}≥max(a_{i,k},a_{k,j})$,k 为$1$~$n$中的任意数,可以与$i,j$相等)

是不是看起来有一点眼熟?

  1. $a_{i,j}=a_{j,i}$,表示无向图
  2. $a_{i,i}=0$,表示无自环
  3. $a_{i,j}≥max(a_{i,k},a_{k,j})$,表示最小生成树

所以,这道题可以用最小生成树去写。

复杂度$O(n^2)$,可以$*$过此题


具体写法

第一个和第二个条件直接$O(n^2)$判断过去就好了,不表

我们重点讲然如何判断第三个条件(敲黑板)

怎么判断这个矩阵是不是最小生成树呢?

我们先把它看做一个邻接矩阵,

建立一个完全图,

如果这个图是的任一个生成树都是最小生成树的话,

则满足题意,输出“MAGIC”。

那么重点在于如何去证明这个完全图的任一个生成树都是最小生成树。

我们可以看一下下面的图

如果$max(a,b)≤c$,那么如果按照最小生成树的方法,应该选择连接$B-A-C$才是正确的连法,

否则这个完全图就不满足题意了。

下面是判断第三个条件的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
for(int i=0;i<n;++i)
{
fa[i]=1;
dis[i]=a[1][i];
}
us[1]=1;
while(true)
{
j=-1;
for(int i=0;i<n;++i)
{
if(!us[i]&&(j==-1||dis[i]<dis[j]))
{
j=i;
}
}
if(j==-1)
{
break;
}
us[j]=1;
for(int i=0;i<n;++i)
{
if(!us[i]&&a[j][i]<dis[i])
{
dis[i]=a[j][i];
fa[i]=j;
}
}
}
d[1]=1;
for(int i=0;i<n;++i)
{
if(!d[i])
{
getf(i);
}
}
for(int i=0;i<n;++i)
{
for(int j=i+1; j<=n; j++)
{
x=i;
y=j;
if(d[y]>d[x])
{
swap(x,y);
}
if(a[x][y]>a[fa[x]][x]&&a[x][y]>a[fa[x]][y])
{
printf("NOT MAGIC");
return 0;
}
}
}

献上我丑陋的AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

const int L=1000000;
char LZH[L];
char *SSS,*TTT;
inline char gc()
{
if (SSS==TTT) TTT=(SSS=LZH)+fread(LZH,1,L,stdin);
return *SSS++;
}
inline int read()
{
int x=0;
char c=gc();
for (;c<'0'||c>'9';c=gc());
for (;c>='0'&&c<='9';c=gc())
x=(x<<1)+(x<<3)+c-48;
return x;
}

template < class T > inline void write(T x)
{
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}

const int FFF=2500+5;

int n,j,x,y,a[FFF][FFF],fa[FFF],us[FFF],dis[FFF],d[FFF];

void getf(int x)
{
if(!d[fa[x]])getf(fa[x]);
d[x]=d[fa[x]]+1;
}

int main()
{
n=read();
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
a[i][j]=read();
if(i==j&&a[i][j]!=0)
{
puts("NOT MAGIC");
return 0;
}//判断第一个条件
if(i>j&&a[i][j]!=a[j][i])
{
puts("NOT MAGIC");
return 0;
}//判断第二个条件
}
}
for(int i=0;i<n;++i)
{
fa[i]=1;
dis[i]=a[1][i];
}
us[1]=1;
while(true)
{
j=-1;
for(int i=0;i<n;++i)
{
if(!us[i]&&(j==-1||dis[i]<dis[j]))
{
j=i;
}
}
if(j==-1)
{
break;
}
us[j]=1;
for(int i=0;i<n;++i)
{
if(!us[i]&&a[j][i]<dis[i])
{
dis[i]=a[j][i];
fa[i]=j;
}
}
}
d[1]=1;
for(int i=0;i<n;++i)
{
if(!d[i])
{
getf(i);
}
}
for(int i=0;i<n;++i)
{
for(int j=i+1; j<=n; j++)
{
x=i;
y=j;
if(d[y]>d[x])
{
swap(x,y);
}
if(a[x][y]>a[fa[x]][x]&&a[x][y]>a[fa[x]][y])
{
printf("NOT MAGIC");
return 0;
}
}
}
puts("MAGIC");
return 0;
}