题意
给你一个n×nn\times nn×n的矩阵AAA,你需要判断这个矩阵是否满足以下条件:
1.Ai,j=Aj,i(1≤i,j≤n)A_{i,j}=A_{j,i}(1\leq i,j \leq n)Ai,j?=Aj,i?(1≤i,j≤n)
2.Ai,i=0(1≤i≤n)A_{i,i}=0(1\leq i \leq n)Ai,i?=0(1≤i≤n)
3.?i,j,k\forall i,j,k?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)Ai,j?≤max(Ai,k?,Aj,k?)(1≤i,j,k≤n),注意这里的i,j,ki,j,ki,j,k并不满足互不相同。
如果满足,输出MAGIC
,否则输出NOT MAGIC
。
子任务:(鼓励大家想正解)
对于全部测试点:n≤2.5×103,ai,j≤109n\leq 2.5\times 10^3,a_{i,j}\leq 10^9n≤2.5×103,ai,j?≤109。
subtask1(1pts):n≤3n\leq 3n≤3。
subtask2(1pts):n≤100n \leq 100n≤100。
subtask3(1pts):?i,j且i≠j\forall i,j且i≠j?i,j且i??=j,有ai,j=Ca_{i,j}=Cai,j?=C,CCC为常数。
subtask4(97pts):无特殊限制。
样例
3
0 1 2
1 0 2
2 2 0
MAGIC
4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0
NOT MAGIC
[没办法了,这图片上传的时候变小了…]
提示
1.合法矩阵显然是邻接矩阵形式,因此这其实可以转化为一个图论问题。
2.其实有一个subtask还是有用的。
3.对于满足条件的图中的任意一个三元组(a,b,c)(a,b,c)(a,b,c),它们之间两条权值最大的边一定相等。
4.在线学习一个[大概是没有学过的]生成树:
最小瓶颈生成树:
无向图 GGG 的一颗瓶颈生成树是这样的一颗生成树,它最大的边权值在 GGG 的所有生成树中是最小的。瓶颈生成树的值为 TTT 中最大权值边的权。
显然最小生成树是一种特殊的最小瓶颈生成树。
算法一: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)Ai,j?>max(Ai,k?,Aj,k?)(1≤i,j,k≤n),如果存在就不合法。
很容易发现一个做法——我们从小到大加入(Ai,j,i,j)(A_{i,j},i,j)(Ai,j?,i,j),对于每个点我们维护二维数组G[i][j]G[i][j]G[i][j]表示现在iii与jjj是否连边。
那么在加入i,ji,ji,j时已经存在(i,k)(i,k)(i,k),(k,j)(k,j)(k,j)的两条边就不合法了。
注意边权相同的,加入没有先后顺序,应该一起加。
直接暴力检查连边还是O(n3)O(n^3)O(n3)。
但是G[i][j]G[i][j]G[i][j]是一个0/1数组,如果我们将第二维压成二进制的话,检查路径就是(G[i]&G[j])(G[i] \& G[j])(G[i]&G[j])。
因此我们用bitset维护第二维。
复杂度:O(n3w)O(\frac{n^3}{w})O(wn3?)
实际测试时间只要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,ji,ji,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)Ai,j?≤mink=1n?{
max(Ai,k?,Aj,k?)}(1≤i,j≤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})\}bi,j?=mink=1n?{
max(Ai,k?,Aj,k?)}。
注意到当k=ik=ik=i时,bi,j=max(Ai,i,Ai,j)=Ai,jb_{i,j}=max(A_{i,i},A_{i,j})=A_{i,j}bi,j?=max(Ai,i?,Ai,j?)=Ai,j?。
因此,bi,j≤Ai,jb_{i,j}\leq A_{i,j}bi,j?≤Ai,j?。
发现了什么?其实bi,j=Ai,jb_{i,j}=A_{i,j}bi,j?=Ai,j?。
易得bi,jb_{i,j}bi,j?的含义就是从iii到jjj任意一条路径的最大边权的最小值。
证明2:从三元环到最小瓶颈生成树
我们先来分析最简单一种情况——三元环的性质。
根据提示3,我们可以发现:三元环的任意一个生成树的最大边权相等。
再根据提示4,最终得出:
三元环的任意一个生成树为最小瓶颈生成树。
而对于一完全图 GGG,它由若干个三元环组成。
对于每一个生成树,虽然有可能三元组 (a,b,c)(a,b,c)(a,b,c) 之间只间接联通,但由证明一得出,环上的边权一定存在于这条联通路径上。
? 因此,我们证明了每个生成树都包含原来完全图 GGG 的所有边权。
? 显然,我们的每颗生成树上的最大边权相等,因此,我们得出:
满足条件的完全图 GGG 满足任意一个生成树为最小瓶颈生成树。并且,对于 GGG 的任意一个子图 G′G'G′, 它的任意一个生成树也一定是一个最小瓶颈生成树。
算法二
有了上面两个结论之后就简单多了。
我们知道最小瓶颈生成树的特殊形态为最小生成树,因此,我们可以先找出原图的最小生成树。
根据证明2,可以得到,在从小到大加边的时候,加完相同的边时每个联通块一定是完全图。
因此维护sizisiz_isizi?(联通块点数),cnticnt_icnti?(联通块边数),加完相同的边暴力判完全图就是了(复杂度不变,这里略过)。
复杂度:O(n2)O(n^2)O(n2)或O(n2log?n)O(n^2 \log n)O(n2logn)(看你用什么做生成树了)。
算法三
与算法二一样,先找出生成树。
基于证明1,对于不在生成树上的边(u,v)(u,v)(u,v),边权一定是最小生成树的路径上最大的,因此我们每次在(u,v)(u,v)(u,v)路径上去掉一条边,变为(fa[u],v)(fa[u],v)(fa[u],v),只要边(fa[u],v)(fa[u],v)(fa[u],v)合法,且满足wu,v≤max?(wfa[u],v,wu,fa[u])w_{u,v}\leq \max(w_{fa[u],v},w_{u,fa[u]})wu,v?≤max(wfa[u],v?,wu,fa[u]?),那么(u,v)(u,v)(u,v)也一定合法。
? [实在是不想再写了…见谅…]
? 复杂度:O(n2)O(n^2)O(n2)或O(n2log?n)O(n^2 \log n)O(n2logn)。
后记
做这道题花了我非常多的时间。
因为网上的博客全都是直接给出最小生成树的结论,没有任何解释和证明。就连官方题解都是莫名其妙的就说可以用最小生成树做…自己想证明方法是在是太难受了啊…
所以如果有问题,请指出。