Codeforces 892E Envy-白红宇

Codeforces 892E Envy

阅读量：5318 次

发布时间：2019-06-14

本文共 1988 字，大约阅读时间需要 6 分钟。

问题描述

小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)，分别表示每张卡片的长度和宽度。

输出格式

输出一行一个整数，即最高的塔的高度，输入数据保证一定存在解。

样例输入

5 16

10 5

5 10

样例输出

解析

不妨将一个矩形放在底下的边视为长，另一边视为宽，若将两条边作为点连起来，为了满足单调递减的条件，每个长只能连向一个宽。那么这就变成了一个边定向问题。一条边的入点作为长，出点作为宽，则每个点的答案贡献为

\((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 
    
     #include 
     
      #include 
      #define N 500002#define int long longusing 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
       
         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;}

转载于:https://www.cnblogs.com/LSlzf/p/11182681.html

你可能感兴趣的文章