Codeforces 892E Envy

問題描述

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

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

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

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

輸入格式

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

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

輸出格式

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

樣例輸入

3
5 16
10 5
5 10

樣例輸出

20

解析

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

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

關于判斷是基環樹還是樹，因為樹有n個點n-1條邊，所以有
\[ \sum_{i=1}^{n}d[i]=2(n-1) \Rightarrow \sum_{i=1}^{n}(d[i]-2)<0 \]
滿足上式的即為樹，否則為基環樹。

代碼

#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;
}