menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[思维]Codeforces632F【Magic Matrix】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论

题目概述

有 $n\times n$ 的矩阵 $a$ ,判断该矩阵是否满足:1. $a_{i,j}=a_{j,i}$ 。2. $a_{i,i}=0$ 。3. $\forall i,j,k,a_{i,j}\le max\{a_{i,k},a_{j,k}\}$ 。

解题报告

神仙题……我们观察第三个式子,会发现这和最小生成树长得很像……

把 $a_{j,k}$ 代成 $max\{a_{j,t},a_{k,t}\}$ ,那么 $a_{i,j}\le max\{a_{i,k},a_{k,t},a_{j,t}\}$ ,然后将 $a_{j,t}$ 又代成 $a_{j,u}$ ……

这样最终可以代成:$a_{i,j}\le max\{a_{i,k_1},a_{k_1,k_2},a_{k_2,k_3},\cdots,a_{k_m,j}\}​$ ,其中 $\{k_m\}​$ 是一个序列,可以认为是一段路径!

也就是说,令 $f_{i,j}$ 表示最小生成树中 $(i,j)$ 路径上的最大值,那么 $\forall i,j,a_{i,j}\le f_{i,j}​$ 。

又因为 $f_{i,j}$ 其实也表示 $(i,j)$ 所有路径中最长边权的最小值,所以 $a_{i,j}\ge f_{i,j}$(否则 $f_{i,j}$ 可以直接给 $a_{i,j}$ )。

根据上面两个条件,就可以得到 $a_{i,j}=f_{i,j}$ ,所以只需要求出最小生成树,并求出 $f_{i,j}$ 即可。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=2500;

int n,a[maxn+5][maxn+5],cst[maxn+5],ID[maxn+5],b[maxn+5][maxn+5];bool vis[maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],w[(maxn<<1)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int st,int x,int pre=0,int MAX=0){
    for (int j=(b[st][x]=MAX,lnk[x]);j;j=nxt[j])
        if (son[j]!=pre) Dfs(st,son[j],x,max(MAX,w[j]));
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) readi(a[i][j]);
    for (int i=1;i<=n;i++) if (a[i][i]) return puts("NOT MAGIC"),0;
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (a[i][j]!=a[j][i]) return puts("NOT MAGIC"),0;
    for (int i=1;i<=n;i++) cst[i]=a[1][i],ID[i]=1;vis[1]=true;
    for (int i=1;i<n;i++){
        int k=-1,MIN=2e9;for (int j=1;j<=n;j++) if (!vis[j]&&cst[j]<MIN) MIN=cst[k=j];
        vis[k]=true;for (int j=1;j<=n;j++) if (!vis[j]&&a[k][j]<cst[j]) cst[j]=a[k][j],ID[j]=k;
    }for (int i=2;i<=n;i++) Add(ID[i],i,cst[i]),Add(i,ID[i],cst[i]);
    for (int i=1;i<=n;i++) Dfs(i,i);
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (a[i][j]!=b[i][j]) return puts("NOT MAGIC"),0;
    puts("MAGIC");return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up