DDOSvoid's Blog

CF 632F Magic Matrix

发表于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

题目描述

http://codeforces.com/problemset/problem/632/F

Solution

首先前两个条件可以暴力判断，然后我们考虑将这个矩阵当成邻接矩阵

然后我们能得到一个信息，对于所有 $(i,j)$，只要权值小于 $(i,j)$ 的边没有将 $i$ 和 $j$ 连通，或者换句话说，不存在一条由权值小于 $(i,j)$ 的边组成的从 $i$ 到 $j$ 的路径，那么这个矩阵一定合法

这个东西可以直接在 $kruskal$ 的过程中判断，时间复杂度 $O(n^2\log {n^2})$

注意到两点直接最大值最小的路径就是最小生成树上两点的路径，那么我们可以用 $prim$ 跑出最小生成树，然后在判断

时间复杂度 $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
#include <vector>
#define maxn 2510
#define ll long long 
using namespace std;

int n, k, g[maxn][maxn];

struct Edge {
    int fr, to, w;

    friend bool operator < (const Edge &u, const Edge &v) { return u.w < v.w; } 
} e[maxn * maxn / 2];

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

inline void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return ;
    fa[fy] = fx;
} 

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; int m = 0; 
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) cin >> g[i][j];
    for (int i = 1; i <= n; ++i) {
        if (g[i][i]) return cout << "NOT MAGIC\n", 0;
        for (int j = i + 1; j <= n; ++j) { 
            if (g[i][j] != g[j][i]) return cout << "NOT MAGIC\n", 0;
            e[++m] = { i, j, g[i][j] }; 
        }
    }
    sort(e + 1, e + m + 1); init_fa(n);
    for (int l = 1, r; l <= m; l = r) {
        r = l; while (e[r].w == e[l].w && r <= m) ++r;
        for (int i = l; i < r; ++i)
            if (find(e[i].fr) == find(e[i].to))
                return cout << "NOT MAGIC\n", 0;
        for (int i = l; i < r; ++i) merge(e[i].fr, e[i].to); 
    } cout << "MAGIC\n";
    return 0;
}