Wuyanru's blog
0%

[QOJ10798] Generate Tree From Polygon

发表于 分类于 ，

感觉其实有点无语这个题（

题目链接。

题意

给定一个由 个点组成的凸多边形，第 个点的坐标为 。

现在有一张 个点的完全图，一条边 的边权是 。

求这张图的最大生成树边权和。

，时限 。

题解

因为要求最大生成树，所以考虑 Boruvka。

这样相当于是我们有若干组点，每一次对于每一个点，需要找出和他不在一组的点里，到他距离最大的点。

直接对组进行分治，这样相当于只需要考虑只有两组点的情况。

现在要对于一组点，找出其往另一组里连的最大的边。

而对于任意一个凸四边形，其边权都是满足四边形不等式的，也就是这个东西有决策单调性。

所以直接分治一下就好了。

时间复杂度 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
using _=__int128;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void write(_ a)
{
    if(a>9) write(a/10);
    putchar(a%10+'0');
}
struct node
{
    int u,v;ll w;
    node(int u=0,int v=0,ll w=0):u(u),v(v),w(w){}
}ed[120005];
struct nod
{
    int id;ll x,y;
    nod(int id=0,ll x=0,ll y=0):id(id),x(x),y(y){}
}a[240005],b[240005];
int fa[120005];
ll x[120005];
ll y[120005];
int id[120005];
vc<int>W[120005];
int n,m,c,cm;
_ ans;
inline int find(int num)
{
    if(fa[num]==num) return num;
    return fa[num]=find(fa[num]);
}
inline ll C(ll a){ return a*a;}
inline void push(int u,int v,ll w)
{
    if(v>n) v-=n;
    if(w>ed[u].w) ed[u]=node(u,v,w);
}
void cdq(nod *a,nod *b,int l,int r,int pl,int pr)
{
    if(l>r) return ;
    int mid=(l+r)>>1;ll ans=-1;int w=-1;
    for(int i=pl;i<=pr;i++)
    {
        if(b[i].id<a[mid].id) continue;
        ll val=C(a[mid].x-b[i].x)+C(a[mid].y-b[i].y);
        if(val>ans) ans=val,w=i;
    }
    // assert(ans>0);
    push(a[mid].id,b[w].id,ans);
    cdq(a,b,l,mid-1,pl,w),cdq(a,b,mid+1,r,w,pr);
}
void cdq(int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);

    int lenA=0,lenB=0;
    for(int i=l;i<=mid;i++) for(int j:W[id[i]]) a[++lenA]=nod(j,x[j],y[j]);
    for(int i=mid+1;i<=r;i++) for(int j:W[id[i]]) b[++lenB]=nod(j,x[j],y[j]);
    sort(a+1,a+lenA+1,[](nod a,nod b){ return a.id<b.id;});
    sort(b+1,b+lenB+1,[](nod a,nod b){ return a.id<b.id;});
    for(int i=1;i<=lenA;i++) a[i+lenA]=a[i],a[i+lenA].id+=n;
    for(int i=1;i<=lenB;i++) b[i+lenB]=b[i],b[i+lenB].id+=n;

    cdq(a,b,1,lenA,1,2*lenB);cdq(b,a,1,lenB,1,2*lenA);
}
int main()
{
    int T=read();
    while(T--)
    {
        n=read();_ ans=0;
        for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(),fa[i]=i;

        while(true)
        {
            c=0;
            for(int i=1;i<=n;i++) W[i].clear();

            for(int i=1;i<=n;i++)
            {
                if(find(i)==i) id[++c]=i;
                W[find(i)].push_back(i);
            }

            if(c==1) break;

            for(int i=1;i<=n;i++) ed[i].w=-1,ed[i].u=i;
            cdq(1,c);

            for(int i=1;i<=n;i++) if(find(i)!=i)
            {
                int to=find(i);
                if(ed[i].w>ed[to].w) ed[to]=ed[i];
                ed[i].w=-1;
            }
            sort(ed+1,ed+n+1,[](node a,node b){ return a.w>b.w;});
            for(int i=1;i<=n;i++) if(ed[i].w>=0)
            {
                int u=find(ed[i].u),v=find(ed[i].v);
                if(u!=v) fa[v]=u,ans+=ed[i].w;
            }
        }
        write(ans);putchar('\n');
    }
    return 0;
}