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 ;
}