問題描述

小Q正在玩一個疊塔的游戲，游戲的目標(biāo)是疊出盡可能高的塔。在游戲中，一共有n張矩形卡片，其中第i張卡片的

長度為a_i，寬度為b_i。小Q需要把所有卡片按一定順序疊成一座塔，要求對于任意一個矩形，它的長度要嚴(yán)格大

于它上邊的任意一個矩形的長度。塔的高度為所有矩形的寬度之和。在游戲中，小Q可以將卡片翻轉(zhuǎn)90度來使用，

而且必須用上全部n張卡片。請寫一個程序，幫助計(jì)算小Q能疊出最高的塔的高度。

輸入格式

第一行包含一個正整數(shù)n(1<=n<=250000)，即卡片的個數(shù)。

接下來n行，每行兩個正整數(shù)a_i,b_i(1<=a_i,b_i<=10^9)，分別表示每張卡片的長度和寬度。

輸出格式

輸出一行一個整數(shù)，即最高的塔的高度，輸入數(shù)據(jù)保證一定存在解。

樣例輸入

3
5 16
10 5
5 10

樣例輸出

20

解析

不妨將一個矩形放在底下的邊視為長，另一邊視為寬，若將兩條邊作為點(diǎn)連起來，為了滿足單調(diào)遞減的條件，每個長只能連向一個寬。那么這就變成了一個邊定向問題。一條邊的入點(diǎn)作為長，出點(diǎn)作為寬，則每個點(diǎn)的答案貢獻(xiàn)為
\((d[i]-1)*val[i]\)，其中\(d[i]\)表示與該點(diǎn)相連的邊數(shù)，減一即為減去一個出邊得到一共做了多少次寬。

注意到每個點(diǎn)僅有一個出邊的性質(zhì)，那么滿足條件的連通塊最后形成的結(jié)構(gòu)為內(nèi)向樹或者內(nèi)向基環(huán)樹。如果是內(nèi)向基環(huán)樹則方案唯一，但如果是樹的話，會有根節(jié)點(diǎn)答案為\(d[root]*val[root]\)，即\(val[root]\)會多算一遍。所以我們應(yīng)選最大的點(diǎn)為根節(jié)點(diǎn)。

關(guān)于判斷是基環(huán)樹還是樹，因?yàn)闃溆衝個點(diǎn)n-1條邊，所以有
\[ \sum_{i=1}^{n}d[i]=2(n-1) \Rightarrow \sum_{i=1}^{n}(d[i]-2)<0 \]
滿足上式的即為樹，否則為基環(huán)樹。

代碼

#include <iostream> #include <cstdio> #include <map> #define N 500002 #define int long long using namespace std; int head[N],ver[N*2],nxt[N*2],d[N],l; int n,i,num,maxx,sum,ans,key[N]; bool vis[N]; map<int,int> val; int read() {char c=getchar();int w=0;while(c<'0'||c>'9') c=getchar();while(c<='9'&&c>='0'){w=w*10+c-'0';c=getchar();}return w; } void insert(int x,int y) {l++;ver[l]=y;nxt[l]=head[x];head[x]=l;d[y]++; } void dfs(int x) {vis[x]=1;maxx=max(maxx,key[x]);sum+=d[x]-2;ans+=(d[x]-1)*key[x];for(int i=head[x];i;i=nxt[i]){int y=ver[i];if(!vis[y]) dfs(y);} } signed main() {n=read();for(i=1;i<=n;i++){int a,b;a=read();b=read();if(!val[a]){val[a]=++num;key[num]=a;}if(!val[b]){val[b]=++num;key[num]=b;}a=val[a];b=val[b];insert(a,b);insert(b,a);}for(i=1;i<=num;i++){if(!vis[i]){maxx=sum=0;dfs(i);if(sum<0) ans+=maxx;}}printf("%lld\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/LSlzf/p/11182681.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 892E Envy的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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