Highest Tower Gym - 101550H（建图，思路）

本文主要是介绍Highest Tower Gym - 101550H（建图，思路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意： n个矩形，要求使得上面矩形宽度严格小于下面矩形，问能够得到的最大高度。

思路：
很巧妙的思路。

1. 首先题目保证一定有解。考虑将每个矩形的边(u,v)设置双向边u->v与v->u，u->v代表选择u为宽，v为高。
2. 那么可以建出一张图，这个图可以分出很多连通分量，不同连通分量意味着每个边都是不同的，那么可以在两个连通分量内分别堆成最高的矩形，然后将两者合并，结果仍然最优。所以对连通分量可以分别考虑
3. 假设连通分量内有n个点，m条边，代表可以堆m个矩形，最多有n个宽度可以用。要满足题意，必须使得每个点出度不大于1，则有 m=n 或者 m=n-1。
4. 这实际意味着这张图是树或者基环树，然后我们要将每个边定向，选择相应的宽高。
5. 当这张图为基环图时，每个点都要分一个度数作为出度（当做宽），剩下度数作为高，所以每个点的贡献为 $(deg[x]-1)\ast val[x]$（度数不作为出度就得作为入度）。
6. 当这张图为树的时候，此时有一个节点的出度为0，我们将这个出度为0的点连到任意其他点，就可以获得这个点的值（此点值作为高），我们可以贪心的选择最大的值。
7. 当$m<n-1$的时候，图不连通。当$m>n$时，要堆$m$个矩形却只有$n$种宽，不合理。本题巧就巧在保证 都能用上。记得写过堆积木的题（三维堆箱子求高），那个题范围比较小可以直接DP。本题2e5，同时加上了巧妙的限制，所以可以用这种建图的方法解决。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
map<int,int>mp;
int cnt,flag,mx;
int vis[maxn],val[maxn];
int head[maxn],nex[maxn],to[maxn],deg[maxn],tot;
ll ans;void add(int x,int y) {if(!mp[x]) mp[x] = ++cnt;if(!mp[y]) mp[y] = ++cnt;val[mp[x]] = x;val[mp[y]] = y;x = mp[x];y = mp[y];deg[x]++;to[++tot] = y;nex[tot] = head[x];head[x] = tot;
}void dfs(int x) {if(vis[x]) return;vis[x] = 1;mx = max(mx,val[x]);ans += 1ll * (deg[x] - 1) * val[x];flag += (deg[x] - 2);for(int i = head[x];i;i = nex[i]) {dfs(to[i]);}
}int main() {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}for(int i = 1;i <= cnt;i++) {if(vis[i]) continue;flag = mx = 0;dfs(i);if(flag < 0) ans += mx;}printf("%lld\n",ans);return 0;
}

这篇关于Highest Tower Gym - 101550H（建图，思路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---