当前位置：首页 > news >正文

fzyzojP3979 -- [校内训练20180914]魔法方阵

news 来源：原创 2024/5/4 13:50:33

原题见CF632F

https://blog.csdn.net/Steaunk/article/details/80217764

这个比较神仙了

点边转化，

把max硬生生转化成了路径最大值，再考虑所有路径最大值的最小值

再通过<=,>=变成=

简单证明一下充要性：
如果都满足f(i,j)=a(i,j)，那么对于路径aij->aik->akj->aij也都满足，所以一定成立

如果存在一个f(i,j)<a(i,j)，那么一定会有某一步a(k1,k3)>max(a(k1,k2),a(k2,k3))，才会使得f(i,j)<a(i,j)，

那么一定也是不合法的了

prim+dfs稳定O(n^2)

网格不光是二分图，网络流，，还可以拆点，点边转化

并且，ai,k->ai,l+al,k的路径拆分有点意思

#include<bits/stdc++.h>
#define il inline
#define reg register int
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
    char ch;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
namespace Miracle{
const int N=5000+5;
const int inf=0x3f3f3f3f;
int v[N][N];
int n;
struct node{
    int nxt,to,val;
}e[2*N];
int hd[2*N],cnt;
void add(int x,int y,int z){
    e[++cnt].nxt=hd[x];
    e[cnt].to=y;
    e[cnt].val=z;
    hd[x]=cnt;
}
int pre[2*N],tot;
bool fl;
int a[N][N];
int dis[N];
int from[N];
bool vis[N];
void prim(){
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(reg i=1;i<=2*n;++i){
        int id=0;
        for(reg j=1;j<=2*n;++j){
            if(!vis[j]&&dis[j]<dis[id]) id=j;
        }
        vis[id]=1;
        //cout<<" add new "<<id<<" "<<from[id]<<" dis "<<dis[id]<<endl;
        if(from[id])add(from[id],id,dis[id]);
        if(from[id])add(id,from[id],dis[id]);
        for(reg j=1;j<=2*n;++j){
            if(vis[j]) continue;
            if(dis[j]>v[id][j]){
                dis[j]=v[id][j];
                from[j]=id;
            }
        }
    }
}
void dfs(int x,int rt,int fa,int mx){
    if(x!=rt&&((rt<=n&&x>n)||(rt>n&&x<=n))){
        //cout<<" checking "<<x<<" "<<rt<<" mi "<<mx<<endl;
        if(a[rt][x-n]!=mx) fl=false;
    }
    for(reg i=hd[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fa) continue;
        dfs(y,rt,x,max(mx,e[i].val));
    }
}
int main(){
    rd(n);
    fl=true;
    memset(v,0x3f,sizeof v);
    for(reg i=1;i<=n;++i){
        for(reg j=1;j<=n;++j){
            rd(a[i][j]);
            if(i==j&&a[i][j]!=0) fl=false;
            if(i>j&&a[i][j]!=a[j][i]) fl=false;
            v[i][j+n]=a[i][j];
            v[j+n][i]=a[i][j];
        }
    }
    if(!fl){
        puts("NOT MAGIC");return 0;
    }
    prim();
//    cout<<" after prim "<<endl;
    for(reg i=1;i<=n;++i){
        if(!fl) break;
        dfs(i,i,0,0);
    }
    if(!fl){
        puts("NOT MAGIC");return 0;
    }
    puts("MAGIC");return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2019/2/3 9:16:23
*/