首页 > 代码库 > （最小生成树）Codeforces Educational Codeforces Round 9 Magic Matrix

（最小生成树）Codeforces Educational Codeforces Round 9 Magic Matrix

2024-09-25 20:19:01   220人阅读

You‘re given a matrix A of size n?×?n.

Let‘s call the matrix with nonnegative elements magic if it is symmetric (so aij?=?aji), aii?=?0 and aij?≤?max(aik,?ajk) for all triples i,?j,?k. Note that i,?j,?k do not need to be distinct.

Determine if the matrix is magic.

As the input/output can reach very huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input

The first line contains integer n (1?≤?n?≤?2500) — the size of the matrix A.

Each of the next n lines contains n integers aij (0?≤?aij?<?109) — the elements of the matrix A.

Note that the given matrix not necessarily is symmetric and can be arbitrary.

Output

Print ‘‘MAGIC" (without quotes) if the given matrix A is magic. Otherwise print ‘‘NOT MAGIC".

Example

Input
3
0 1 2
1 0 2
2 2 0
Output
MAGIC
Input
2
0 1
2 3
Output
NOT MAGIC
Input
4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0
Output
NOT MAGIC

定义中的前两个条件直接检验即可，对于第三个条件等价于从i到j的任意路径的最大值的最小值与a[i][j]最小。

利用kruskal中利用的性质，每次选的都是最小的边，故i到j上述的值一定是在最小生成树中最小。
故只需要先生成最小生成树，再算出此时的任意i与j间“任意路径的最大值的最小值”，与a[i][j]逐个比较即可。

  1 #include <iostream>
  2 #include <string>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <queue>
  8 #include <set>
  9 #include <map>
 10 #include <list>
 11 #include <vector>
 12 #include <stack>
 13 #define mp make_pair
 14 #define MIN(a,b) (a>b?b:a)
 15 #define rank rankk
 16 //#define MAX(a,b) (a>b?a:b)
 17 typedef long long ll;
 18 typedef unsigned long long ull;
 19 const int MAX=2505;
 20 const ll INF=1e18+5;
 21 const int B=1024;//桶的大小
 22 const double M=4e18;
 23 using namespace std;
 24 const int MOD=1e9+7;
 25 typedef pair<int,int> pii;
 26 int n,cnt;
 27 int a[MAX][MAX];
 28 bool vi[MAX];
 29 vector <int> road[MAX];
 30 bool res;
 31 int mst[MAX][MAX];
 32 
 33 /*
 34     kruskal最小生成树算法
 35     按照边的权值的顺序从小到大看一遍，如果不产生圈（重边也考虑在内）
 36     就把当前这条边加入到生成树中
 37     是否产生圈只需看两点之前是否在同一连通分量里
 38     使用并查集判断是否属于同一个连通分量
 39 */
 40 #define rank rankk  //由于与某个库名称相同，故事先define
 41 /*
 42 并查集
 43 复杂度为阿克曼函数的反函数，比O(log(n))还快
 44 */
 45 
 46 int par[MAX];//父亲
 47 int rank[MAX];//树的高度
 48 //初始化n个元素
 49 void init(int n)
 50 {
 51     for(int i=0;i<n;i++)
 52     {
 53         par[i]=i;
 54         rank[i]=0;
 55     }
 56 }
 57 //查询树的根，期间加入了路径压缩
 58 int find(int x)
 59 {
 60     if(par[x]==x)
 61         return x;
 62     else
 63         return par[x]=find(par[x]);
 64 }
 65 //合并x和y所属的集合
 66 void unite(int x,int y)
 67 {
 68     x=find(x);
 69     y=find(y);
 70     if(x==y)
 71         return ;
 72     if(rank[x]<rank[y])
 73         par[x]=y;
 74     else
 75     {
 76         par[y]=x;
 77         if(rank[x]==rank[y])
 78             rank[x]++;
 79     }
 80 }
 81 //判断x和y是否属于同一个集合
 82 bool same(int x,int y)
 83 {
 84     return find(x)==find(y);
 85 }
 86 /*
 87 建立结构体记录边
 88 */
 89 struct edge
 90 {
 91     int u,v,cost;
 92 };
 93 /*储存边的数组*/
 94 edge es[MAX*MAX/2];
 95 int V,E;//顶点数、边数
 96 bool cmp(const edge &e1,const edge &e2)
 97 {
 98     return e1.cost<e2.cost;
 99 }
100 void kruskal(edge *e,int edge_num,int vertice_num)//e为存储边的数组，下标从0开始
101 {
102     sort(e,e+edge_num,cmp);//按照edge.cost顺序从小到大排序
103     init(vertice_num+2);//初始化并查集
104     for(int i=1;i<=vertice_num;i++)
105         road[i].clear();
106 //    ll re=0;
107     for(int i=0;i<edge_num;i++)
108     {
109         edge tem=e[i];
110         if(!same(tem.u,tem.v))
111         {
112             road[tem.u].push_back(tem.v);
113             road[tem.v].push_back(tem.u);
114             unite(tem.u,tem.v);
115 //            re+=(ll)tem.cost;
116         }
117     }
118 //    return re;
119 }
120 void dfs(int lo,int st,int nowmax)
121 {
122     vi[lo]=true;
123     mst[st][lo]=nowmax;
124     for(int i=0;i<road[lo].size();i++)
125     {
126         int to=road[lo][i];
127         if(!vi[to])
128             dfs(to,st,max(nowmax,a[lo][to]));
129     }
130 }
131 bool check1(int x)
132 {
133     for(int i=1;i<=x;i++)
134         if(a[i][i])
135             return false;
136     for(int i=1;i<=x;i++)
137         for(int j=i+1;j<=x;j++)
138             if(a[i][j]!=a[j][i])
139                 return false;
140     return true;
141 }
142 int main()
143 {
144     while(~scanf("%d",&n))
145     {
146         res=true;
147         cnt=0;
148         edge tem;
149         for(int i=1;i<=n;i++)
150             for(int j=1;j<=n;j++)
151                 {
152                     scanf("%d",&a[i][j]);
153                     if(j>i)
154                     {
155                         tem.u=i;tem.v=j;tem.cost=a[i][j];es[cnt++]=tem;
156                     }
157                 }
158         if(!check1(n))
159         {
160             printf("NOT MAGIC\n");continue;
161         }
162         kruskal(es,cnt,n);
163         for(int i=1;i<=n;i++)
164         {
165             memset(vi,false,sizeof(vi));
166             dfs(i,i,0);
167         }
168         for(int i=1;i<=n;i++)
169         {
170             for(int j=1;j<=n;j++)
171             {
172                 if(mst[i][j]!=a[i][j])
173                     res=false;
174                 if(!res)
175                     break;
176             }
177             if(!res)
178                 break;
179         }
180         if(res)
181             printf("MAGIC\n");
182         else
183             printf("NOT MAGIC\n");
184     }
185 }

 

（最小生成树）Codeforces Educational Codeforces Round 9 Magic Matrix


联系
我们