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

原题见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*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=+;

const int inf=0x3f3f3f3f;

int v[N][N];

int n;

struct node{

    int nxt,to,val;

}e[*N];

int hd[*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[*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[]=;

    for(reg i=;i<=*n;++i){

        int id=;

        for(reg j=;j<=*n;++j){

            if(!vis[j]&&dis[j]<dis[id]) id=j;

        }

        vis[id]=;

        //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=;j<=*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=;i<=n;++i){

        for(reg j=;j<=n;++j){

            rd(a[i][j]);

            if(i==j&&a[i][j]!=) 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 ;

    }

    prim();

//    cout<<" after prim "<<endl;

    for(reg i=;i<=n;++i){

        if(!fl) break;

        dfs(i,i,,);

    }

    if(!fl){

        puts("NOT MAGIC");return ;

    }

    puts("MAGIC");return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/2/3 9:16:23

*/

或者：

i,j,k三排点

这个还是常数太大

排序已经用256作为基底基排了

还是2s左右

还是第一个吧

这个思路主要是考虑单个三元环的边出现的大小关系

充要性显然