BZOJ

分析

感觉好神仙啊。

对于一个长为 $a$ 、宽为 $b$ 的矩形,连一条 $(a,b)$ 的双向边。

问题转换为给所有边定向,使得所有点的入度为 $1$ 且出度乘权值的和最大。

考虑所有连通块,可以发现不会出现 $m>n$ 的情况。也就是说每个连通块只可能是树或基环树。

如果是一棵树,画图可以得到答案为 $\displaystyle w_{root}+\sum w_i(deg_i-1)$ ,那么把权值最大的点作为 $root$ 即可。

如果是一棵基环树,画图可以得到答案为 $\displaystyle\sum w_i(deg_i-1)$ 。

具体实现大概是这样的:首先离散化,然后维护一个并查集,顺便维护一下连通块内有没有环和权值最大的点,最后计算答案即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int n,top;
int a[N],b[N],S[N];
int deg[N],f[N],cir[N],mx[N];

inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

int main() {
    n=read();
    for (re int i=1;i<=n;++i) {
        S[++top]=a[i]=read();
        S[++top]=b[i]=read();
    }
    sort(S+1,S+top+1); top=unique(S+1,S+top+1)-S-1;
    for (re int i=1;i<=n;++i) {
        a[i]=lower_bound(S+1,S+top+1,a[i])-S;
        b[i]=lower_bound(S+1,S+top+1,b[i])-S;
    }
    for (re int i=1;i<=top;++i) f[i]=i,mx[i]=i;
    for (re int i=1;i<=n;++i) {
        ++deg[a[i]],++deg[b[i]];
        int p=find(a[i]),q=find(b[i]);
        if (p==q) cir[p]=1;
        else f[p]=q,cir[q]|=cir[p],mx[q]=max(mx[p],mx[q]);
    }
    ll ans=0;
    for (re int i=1;i<=top;++i) {
        ans+=1ll*(deg[i]-1)*S[i];
        if (i==f[i]&&!cir[i]) ans+=S[mx[i]];
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2020 年 05 月 04 日 02 : 49 PM