codeforces 632f 最小瓶颈树

题意是给你一个n*n的矩阵，让你判断是否满足以下条件：

1.a[i][j]=a[j][i],a[i][i]=0

2.对于任意i,j,对于任意k，有a[i]][j]<=max(a[i][k],a[j][k]).

思路:a[i][j]<=max(a[i][k],a[j][k])=max(a[i][k],a[k][j]),仔细观察发现它具有传递性,即a[i][l]<=max(a[i][j],a[j][k],a[k][l]).构造完全图，则转化为从i到j的任意一条路径，都有a[i][j]<=该路径边的最大值,即所有路径中边的最大值的最小值>=a[i]][j],又因为a[i][j]本来就是一条路径，因此a[i][j]就是这个最小值。因此满足题意的充要条件是从i到j的最小瓶颈路对应权值等于a[i][j].

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#define LL long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int N=;
const int inf=;
struct EDGE
{
    int u,v;
    LL w;
    EDGE(){}
    EDGE(int u,int v,LL w):u(u),v(v),w(w){}
    bool operator <(const EDGE& b)const
    {
        return w<b.w;
    }
}edge[N*N/];
vector<int> G[N];
int fa[N];
int temp[N];
LL a[N][N],maxcost[N][N];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int n,ct;

void dfs(int u,int f)
{
    temp[++ct]=u;
    for(int i=;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==f)continue;
        for(int j=;j<=ct;j++)
        {
            int t=temp[j];
            maxcost[t][v]=maxcost[v][t]=max(maxcost[t][u],a[u][v]);
        }
        dfs(v,u);
    }
}
int main()
{
    //freopen("a.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        for(int i=;i<=n;i++)
            for(int j=;j<=n;j++)scanf("%I64d",&a[i][j]);
        int ok=;
        for(int i=;i<=n;i++)
            if(a[i][i]>)ok=;
        int m=;
        for(int i=;i<=n;i++)
            for(int j=i+;j<=n;j++)
            {
                if(a[i][j]!=a[j][i])ok=;
                edge[++m]=EDGE(i,j,a[i][j]);
            }
        if(ok==)
        {
            puts("NOT MAGIC");continue;
        }
        for(int i=;i<=n;i++)fa[i]=i,G[i].clear();
        sort(edge+,edge+m+);
        int k=;
        for(int i=;i<=m;i++)
        {
            if(k==n-)break;
            int u=find(edge[i].u),v=find(edge[i].v);
            if(u==v)continue;
            fa[u]=v;k++;
            G[edge[i].u].push_back(edge[i].v);
            G[edge[i].v].push_back(edge[i].u);
        }
        memset(maxcost,,sizeof(maxcost));
        ct=;
        dfs(,-);
        for(int i=;i<=n;i++)
        {
            for(int j=;j<=n;j++)if(a[i][j]!=maxcost[i][j])ok=;
        }
        if(ok==)puts("NOT MAGIC");
        else puts("MAGIC");
    }
    return ;
}