題目鏈接：點擊查看

題目大意：給出 $n$ 個葉子結(jié)點和一個 $n?n$ 的 $LCA$ 矩陣，其中 $LCA$ 表示的是最近公共祖先節(jié)點的權(quán)值，現(xiàn)在需要構(gòu)造出一棵自頂向下權(quán)值嚴格遞減的樹

題目分析：
參考至：https://blog.csdn.net/liufengwei1/article/details/114298063

思路就是貪心去合并，類似于哈夫曼樹那樣，將所有的 $LCA$ 從小到大排序，然后貪心去加

一開始以為所有點權(quán)都不一樣，后來意識到是每一條鏈上的點權(quán)互不相同，這也就導(dǎo)致了不同鏈上的點權(quán)有可能是相同的，為了解決這個問題我們需要在排序的時候，當(dāng)權(quán)值相同時，按照編號排序，不然會出現(xiàn)下述情況：

假設(shè)原本 $5$ 為根節(jié)點， $1,2,3,4$ 為其四個兒子，也是葉子節(jié)點，顯然四個葉子結(jié)點兩兩之間的 $LCA$ 都是 $5$，如果我們先處理的 $(1,2)$，此時正確的產(chǎn)生了兩條邊 $5?>1$ 和 $5?>2$，接下來如果繼續(xù)處理點對 $(3,4)$ 的話，按照我們的算法，會產(chǎn)生出一個點 $6$ 且產(chǎn)生出兩條邊 $6?>3$ 和 $6?>4$，到最后會發(fā)現(xiàn)構(gòu)造出來的并不是一棵樹而是一個森林

假如我們按照編號排序，按照順序依次處理點對 $(1,2),(1,3),(1,4)$ 就不會出現(xiàn)上述問題了

剩下的就只需要維護連通性問題就可以了，這個用并查集就可以輕松解決

代碼：

// Problem: D. Dogeforces // Contest: Codeforces - Educational Codeforces Round 105 (Rated for Div. 2) // URL: https://codeforces.com/contest/1494/problem/D // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int c[N],f[N],fa[N]; struct Node {int i,j,val;bool operator<(const Node& t)const {if(val!=t.val) {return val<t.val;} else {if(i!=t.i) {return i<t.i;} else {return j<t.j;}}} }; int find(int x) {return f[x]==x?x:f[x]=find(f[x]); } void init() {for(int i=0;i<N;i++) {f[i]=i;} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int n;read(n);vector<Node>node;for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {int x;read(x);if(i<j) {node.push_back({i,j,x});} else {c[i]=x;}}}sort(node.begin(),node.end());int cnt=n;for(auto it:node) {int u=it.i,v=it.j,val=it.val;int xx=find(u),yy=find(v);if(xx==yy) {continue;}if(c[xx]<c[yy]) {swap(xx,yy);}//c[xx]>=c[yy]if(val==c[xx]) {//不用建新點f[xx]=f[yy]=fa[xx]=fa[yy]=xx;} else {c[++cnt]=val;f[xx]=f[yy]=fa[xx]=fa[yy]=cnt;}}cout<<cnt<<endl;for(int i=1;i<=cnt;i++) {printf("%d ",c[i]);}puts("");for(int i=1;i<=cnt;i++) {if(find(i)==i) {cout<<i<<endl;}}for(int i=1;i<=cnt;i++) {if(find(i)!=i) {printf("%d %d\n",i,fa[i]);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1494D Dogeforces(贪心+构造)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。