题解：P9030 [COCI2022-2023#1] Berilij（暂无spj）

· · 题解

推荐在 cnblogs 上阅读。

Solution

P9030 [COCI2022-2023#1] Berilij

本题解转载翻译自官方题解：COCI 2022/2023 CONTEST 1

Part 1

让我们定义图形 G，顶点代表飞船，边代表两艘飞船外部接触的情况。此外，让边的边权成为它所连接的圆之间的距离。

现在的任务等同于为顶点找到非负值，使得每条边所连接的两个顶点值之和等于这条边的边权，其中顶点值的平方和尽可能小。

如果顶点 (i, j) 与边权为 w_{i,j} 的边相连，则顶点值的条件 v_i \geq 0，v_j \geq 0 与 v_i + v_j = w_{i,j} 成立。

Part 2

在 Subtask 1 中，G 是一个奇环。由于我们可以计算出每条边的值 w_{i,j}，所以我们可以唯一确定环中第二个顶点的值。

现在我们尝试将第一个顶点的值增加 x。为了满足条件，我们现在需要减少第二个顶点的值，然后增加第三个顶点的值……以此类推，直到我们绕回第一个顶点，新的条件是它的值必须是 a-x。

由于 x = a - x，我们可以唯一确定 x 为 x = \frac{a}{2}。

现在我们只需检查将 \frac{a}{2} 替换为第一个顶点的值是否会导致所有其他顶点的值为非负值。

Part 3

在 Subtask 3 中，G 是一个森林，但只需对每棵树分别求解即可。

为了满足任务的条件，我们现在可以唯一确定每个顶点 i 的值为线性多项式 \pm x + c_i，其中 c_i 是一个常数，其值等于从顶点 i 到根的各条边的交替边权之和。

由于每个值都必须是非负值，因此 x + c_i 的顶点为 x 设定了下限，而 -x + c_i 的顶点为 x 设定了上限。如果上限小于下限，则无解。为了确定顶点值平方和最小的 x，让我们求出每个顶点的线性多项式的平方和。结果是二次多项式 ax^2 + bx + c。

注意，a 等于树的大小，因此二次多项式的最小值为 x =-\frac{b}{2a}。由于这个表达式中没有使用 c，而 b 等于每个顶点的 -2s_ic_i 之和，其中 s_i 是多项式 \pm x + c_i 中 x 前面的符号，因此我们可以计算出 -\frac{b}{2a}，而无需将任何数字平方。如果 x = -\frac{b}{2a} 在下限和上限之间，则 x 就是我们的解，否则我们取上限或下限中更接近 -\frac{b}{2a} 的值。

Part 4

对于完整的解决方案，让我们按照 Subtask 3 的解决方案来解决任意生成树上每个分量的任务。

我们注意到，在 Subtask 3 的解法中，从根开始偶数深度的每个顶点的多项式是 x + c_i，而奇数深度的每个顶点的多项式是 -x + c_i。由于偶环连接不同深度奇偶性的顶点，它们只增加了 (+x+c_i)+(-x+c_j ) = w_{i,j} 形式的条件，换句话说 c_i + c_j = w_{i,j}。奇环连接深度奇偶性相同的顶点，并增加了 (\pm x + c_i) + (\pm x + c_j ) = w_{i,j} 形式的条件，换句话说，\pm x =\frac{1}{2} (w_{i,j} - c_i - c_j)，与 Subtask 1 一样，x 的解只有一个。

时空分析

所述算法的时间复杂度为 O(n+m)。另外，该任务也可以通过更好的三元搜索实现来解决，复杂度为 O((n+m)log(C\epsilon ^{-1}))，其中 C 为坐标的最大绝对值 C = 10^4，\epsilon 为所需精度。

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define pb push_back
#define ft first
#define sd second
#define po(x) ((x)*(x))

const int MAXN=1e5+5;
const ld eps=1e-8;

int n,m;
ld sz[MAXN];
ld ans[MAXN];
ld vl[MAXN],A,B,C;
ld b[MAXN],c[MAXN];
ld lf[MAXN],rg[MAXN];
int rot[MAXN],dep[MAXN];
bool fitr[MAXN],vis[MAXN];
vector<int> Rt;
pair<ld,ld> a[MAXN];
struct edge
{
    int u,v,nxt;
    bool ontr;
    ld w;
}E[MAXN];
int su=1,hd[MAXN];

void add(int u,int v,ld w)
{
    E[++su]={u,v,hd[u],0,w},hd[u]=su;
}

ld dis(int x,int y)
{
    return sqrt(po(a[x].ft-a[y].ft)+po(a[x].sd-a[y].sd));
}

void findtree(int x,int rt)
{
    sz[rt]++;
    rot[x]=rt;
    fitr[x]=1;
    for(int i=hd[x];i;i=E[i].nxt)
    {
        int v=E[i].v;
        ld d=E[i].w;
        if(fitr[v]) continue;
        E[i].ontr=E[i^1].ontr=1;
        dep[v]=dep[x]+1;
        vl[v]=d-vl[x];
        C+=po(vl[v]);
        if(dep[v]&1)
            rg[rt]=min(rg[rt],vl[v]),b[rt]-=2*vl[v];
        else
            lf[rt]=max(lf[rt],-vl[v]),b[rt]+=2*vl[v];
        if(rg[rt]+eps<=lf[rt])
        {
            puts("NE");
            exit(0);
        }
        findtree(v,rt);
    }
}

void pushans(int x)
{
    vis[x]=1;
    for(int i=hd[x];i;i=E[i].nxt)
    {
        int v=E[i].v;
        if(vis[v]||E[i].ontr==0) continue;
        if(dep[v]&1)
            lf[v]=rg[v]=vl[v]-rg[rot[v]];
        else
            lf[v]=vl[v]+lf[rot[v]],rg[v]=vl[v]+rg[rot[v]];
        pushans(v);
    }
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%Lf%Lf",&a[i].ft,&a[i].sd);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y,dis(x,y));
        add(y,x,dis(x,y));
    }
    for(int i=1;i<=n;i++)
    {
        if(fitr[i]) continue;
        vl[i]=0;
        rg[i]=LDBL_MAX;
        findtree(i,i);
        Rt.pb(i);
    }
    for(int i=2;i<=su;i+=2)
    {
        if(E[i].ontr) continue;
        int X=E[i].u,Y=E[i].v;
        if((dep[X]&1)==(dep[Y]&1))
        {
            ld x=(E[i].w-(vl[X]+vl[Y]))/2;
            if(dep[X]&1)
                x*=-1.0;
            int rt=rot[X];
            ld l=lf[rt],r=rg[rt]; 
            if(x+eps<=l||r+eps<=x)
                return puts("NE"),0;
            lf[rt]=rg[rt]=x;
        }
        else
        {
            if(abs(vl[X]+vl[Y]-E[i].w)>eps)
                return puts("NE"),0;
        }
    }

    for(int i:Rt)
    {
        A=sz[i],B=b[i],C=c[i];
        ld x=-B/(2*A);
        ld l=lf[i],r=rg[i];
        if(x+eps<=l|abs(x-l)<eps)
            rg[i]=lf[i];
        else if(r+eps<=x||abs(x-r)<eps)
            lf[i]=rg[i];
        else
            lf[i]=rg[i]=x;
        pushans(i);
    }

    printf("DA\n");
    for(int i=1;i<=n;i++) printf("%.6Lf\n",abs(lf[i]));

    return 0;
}