https://codeforces.com/contest/1494/problem/D
因為上級嚴格比下級大，把a[i][j]從小到大排序，然后就能從下往上構造了,并查集模擬一下
注意排序的同時，還要把i,j排序，也就是一堆相同的值中，先把i的全部給構造完了，這樣就不會出現沖突了
upd:有人問我把i,j排序是為啥，我還是舉個栗子
比如1 2 3 4都是父親是5，但是你在排序的時候搞出了1 2父親是5，然后處理3 4，發現他們的父節點都是他們自己，所以搞出個新節點父親6，最后發現1,3的父親還是權值和5,6一樣，就會出問題，相當于多創建了一個點，但如果一開始排序就先 1 2 ,1 3,1 4,就會只有一個父親5
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxl=5e5+10;
int n,m,k,cnt,tot,cas,ans;
int a[510][510],c[maxl],f[maxl],fa[maxl];
struct node
{
int val,i,j;
}b[510*510];
bool vis[maxl];
char s[maxl];
inline bool cmp(const node &a,const node &b)
{
if(a.val==b.val)
{
if(a.i==b.i)
return a.j<b.j;
return a.i<b.i;
}
return a.val<b.val;
}
inline void prework()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if(i<j)
b[++cnt]=node{a[i][j],i,j};
else if(i==j)
c[i]=a[i][j],f[i]=i;
}
sort(b+1,b+1+cnt,cmp);
}
inline int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
inline void mainwork()
{
tot=n;
for(int i=1;i<=cnt;i++)
{
int l=find(b[i].i),r=find(b[i].j);
if(l==r)
continue;
int top=max(c[l],c[r]);
if(top==b[i].val)
{
if(c[l]==b[i].val)
f[r]=l,fa[r]=l;
else
f[l]=r,fa[l]=r;
}
else if(top<b[i].val)
{
++tot;
f[tot]=tot;c[tot]=b[i].val;
f[l]=f[r]=tot;fa[l]=fa[r]=tot;
}
}
}
inline void print()
{
printf("%d\n",tot);
for(int i=1;i<=tot;i++)
printf("%d%c",c[i]," \n"[i==tot]);
int rt=0;
for(int i=1;i<=tot;i++)
if(find(i)==i)
rt=i;
printf("%d\n",rt);
for(int i=1;i<=tot;i++)
if(find(i)!=i)
printf("%d %d\n",i,fa[i]);
}
int main()
{
int t=1;
//scanf("%d",&t);
for(cas=1;cas<=t;cas++)
{
prework();
mainwork();
print();
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/265999.html
標籤：其他
上一篇：STM32新建工程