计蒜客 17417 Highest Tower（思维+图论）

题解：

实际上一个可行解即选取长和宽的一个，使得最后每一组选第一维的数值都不同

在此基础上，使得另一维的和最大。

然后建立图论模型

对于每一个方块，在a和b之间连边。

对于选择的方案，如果选择a->b，那么就是以a为底，b为高

所以最后的图一定要满足所有点的出度为1（出度为2就有重复了）

基于这个我们发现只有两种情况。

1、图中含有环，实际上所有边的方向都是固定的，答案就是每个点的入度*每个点的值加起来。

2、图中不含环（树的结构），那么实际上可以选取一个点为根，根的答案可以额外计算。所以就选取树中值最大的那个点为根即可。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <map>

using namespace std;

const int maxn = 5e5 + ;

vector<int> G[maxn];

map<int, int> M;

long long m, N, Max, ans;

int vis[maxn], v[maxn];

void dfs(int x){

    if(vis[x]) return;

    vis[x] = ;

    m += G[x].size(); N++; Max = max(Max, (long long)v[x]);

    ans += (G[x].size()-)*v[x];

    for(auto to : G[x]) dfs(to);

}

int n, x, y, tot;

int main()

{

    scanf("%d", &n);

    for(int i = ; i <= n; i++){

        scanf("%d %d", &x, &y);

        if(!M[x]){

            M[x] = ++tot;

            v[tot] = x;

        }

        if(!M[y]){

            M[y] = ++tot;

            v[tot] = y;

        }

        G[M[x]].push_back(M[y]);

        G[M[y]].push_back(M[x]);

    }

    memset(vis, ,   sizeof(vis));

    for(int i = ; i <= tot; i++){

        if(!vis[i]) {

            N = ;

            m = ;

            Max = ;

            dfs(i);

            if(m/ == N-) ans += Max;

        }

    }

    cout<<ans<<endl;

    return ;

}