解析
这是个有趣的建图题啊.
首先我们可以发现,宽度严格递增是没什么用的.
因为实际上我们在旋转完以后,
矩形的顺序是可以随便排的.
因此只要保证宽度互不相同就行了.
然后,我们对长和宽离散化,对于每个值建一个点.
拿样例举个例子:
先把样例放出来:
3
5 16
10 5
5 10
然后建图(因为方便看所以没离散化):
接着,对于每个长,宽为(a,b)的矩形,
我们在(a,b)间连一条边.
那么图就成了这个亚子:
因为有两个矩形都是((5,10)),所以有两条边.
接着,我们定义边的方向是由宽到长.
这里的宽指的是与其它矩形相邻的边,而长是对答案的贡献
所以,矩形的旋转就成了边的定向.
而这样连边后有这样几条性质:
-
每个点的出度最多为一.
这是因为要保证宽都不同,所以每个数最多做一次宽.
-
边数(m)小于等于点数(n).
感性理解一下,因为每个边一定是一个点的出边,根据性质1就可证明.
-
设(i)点的出度为(d[i]),价值为(val[i]),则每个点的贡献至少为((d[i]-1)*val[i]).
这是因为每个点连的边表示它作为长或宽,而每个点最多做一次宽.
然后,我们再分析每个连通块,
当边数等于点数时,这显然是一棵基环树,
所以连通块里的点的贡献就为(sumlimits_i(d[i]-1)*val[i]).
而当边数等于点数减一时,就成了一棵树,
而根节点的出度就为0.
所以我们只要取权值最大的点作为根就行了.
所以贡献为(sumlimits_i(d[i]-1)*val[i])+maxlimits_i(val[i]))
用dfs统计每个连通块就行了.
但这里有一个神奇的操作,
对于一个连通块,我们设(sum=sumlimits_i(d[i]-2)),
若(sum<0),则这是一颗树.
因为我们设点数为(n),
边数为(frac{1}{2}sumlimits_id[i])(因为连的是双向边).
而(sum=sumlimits_id[i]-2n)
就等于边数减点数*2.
而我们只需要比较大小就行了(所以不在乎*2);
code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#define ll long long
#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
using namespace std;
inline int read(){
int sum=0,f=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return f*sum;
}
const int N=500001;
struct edge{int to,next;}e[N<<1];
int n,maxn,sum,ind[N],v[N];
int head[N],cnt=0;
int val[N],tot=0;
ll ans;
map <int,int> mp;
inline void add(int x,int y){
ind[y]++;e[++cnt]=(edge){head[x],y};head[x]=cnt;
}
inline void dfs(int x){
if(v[x]) return ;v[x]=1;
ans+=1ll*(ind[x]-1)*val[x];sum+=ind[x]-2;maxn=max(maxn,val[x]);
for(int i=head[x];i;i=e[i].to) dfs(e[i].next);
}
int main(){
n=read();
for(int i=1;i<=n;i++){
int x=read(),y=read();
if(!mp[x]){mp[x]=++tot;val[tot]=x;}
if(!mp[y]){mp[y]=++tot;val[tot]=y;}
x=mp[x];y=mp[y];
add(x,y);add(y,x);
}
for(int i=1;i<=tot;i++){
if(v[i]) continue;
maxn=sum=0;
dfs(i);
if(sum<0) ans+=maxn;
}
printf("%lld
",ans);
return 0;
}