题解 - Vijos

3

孙鹤鸣 (sunheming) LV 10 @ 2020-10-31 10:51:06

思路一：朴素想法，在所有切点间暴力建边对于每一个询问顺时针逆时针交替搜索。

时间复杂度：\(O(玄学)\)

思路二：不难发现此题的每组询问之间有且仅有两条路径，
且这两条路径之和为路径上所有经过的圆的周长之和。

于是想到求出任意一条路径
，然后使用路径上所有经过的圆的周长之和减去这条路径的长度得到另一条路径长度，再比较大小。

将每个圆看作一个点，两圆相切则连边，不难看出这是一棵树。

将最大的圆代表的点看做根节点，
则其实一条路径上所有经过的圆就是这两个点的LCA所经过的点代表的圆，
所以我们可以通过LCA求路径的方式快速求出使用路径上所有经过的圆的周长之和。

然后再进一步，
其实两点间路径也可以通过类似的方式
（比如定义一个标准方向，即在深度为偶数的圆上顺时针走，
深度为奇数的圆上顺时针走）。

然后就可以发现其实一条路径可以分为五部分，
即在询问中一个给定的节点（圆）由给定幅角到与它父亲节点（圆）的切点按照标准方向走的路径、
这个给定的节点（圆）与它父亲节点（圆）的切点到给定的两个节点的LCA（圆）按照标准方向走的路径、
在给定的两个节点的LCA（圆）上按照标准方向走的路径，
另一个给定的节点（圆）与它父亲节点（圆）的切点到给定的两个节点的LCA（圆）按照逆标准方向走的路径、
这个给定的节点（圆）由给定幅角到与它父亲节点（圆）的切点按照逆标准方向走的路径。

可能上一段看起来有点冗长，则咱们来看点直观的：

箭头代表这个圆的标准方向，则从\(A\)点到\(B\)点的路径可以分为五段，即红段、橙段、黄段、绿段（你没看错那就是一个点），蓝段。

然后得到答案就很简单啦。

但是注意还有两种情况，即一个圆是另一个圆父亲的情况或在同一圆上的情况，需单独考虑，由于比较简单，留给读者自己思考~~其实是我懒。~~

下面上我冗长的代码（含注释）

#include<bits/stdc++.h>
using namespace std;
const double pi=3.14159265358979323846;
int nex[6005],beg[6005],to[6005],r[3005],n,m,t,e,s,ee[3005];
struct T{
    double x,y,sonf[15],faf,wtcl;
    int d,fa[25],sn,snn,son[15];
}tree[3005];//定义节点，sonf、faf为儿子节点（圆）、父亲节点（圆）的幅角
void add(int x,int y){
    to[++e]=y;
    nex[e]=beg[x];
    beg[x]=e;
}//链式前向星
double dist(int d,double x,double y){
    if(x>y)return (2*pi-x+y)*r[d];
    return (y-x)*r[d];
}//计算两点在尺寸为d的圆上逆时针距离
void dfs(int s){
    for(int i=1;(1<<i)<=tree[s].d;i++)
        tree[s].fa[i]=tree[tree[s].fa[i-1]].fa[i-1];
    for(int i=beg[s];i;i=nex[i])dfs(to[i]);
}//倍增预处理
void dfs2(int s){
    for(int i=1;i<=tree[s].sn;i++)
        if(tree[s].d%2==0){ 
            tree[tree[s].son[i]].wtcl=
                tree[s].wtcl+dist(tree[s].d,tree[s].sonf[i],tree[s].faf);
            dfs2(tree[s].son[i]);
        }
        else {
        tree[tree[s].son[i]].wtcl=
            tree[s].wtcl+dist(tree[s].d,tree[s].faf,tree[s].sonf[i]);
            dfs2(tree[s].son[i]);
        }
}//标准方向的距离预处理
int lca(int a,int b){
    if(tree[a].d>tree[b].d)
        swap(a,b);
    for(int i=20;i>=0;i--)
        if(tree[a].d+(1<<i)<=tree[b].d)
            b=tree[b].fa[i];
    if(a==b)return -1;
    for(int i=20;i>=0;i--)
        if(tree[a].fa[i]!=tree[b].fa[i]){
            a=tree[a].fa[i];
            b=tree[b].fa[i];
        }
    return tree[a].fa[0];
}//LCA
int main(){
    scanf("%d%d%d",&n,&m,&t);
    r[0]=1e5;
    ee[0]=1e5;//ee是r的前缀和
    for(int i=1;i<=n;i++)
        scanf("%d",&r[i]),ee[i]=ee[i-1]+r[i];
    s=1;//根节点为1
    for(int i=1;i<=m;i++){
        scanf("%lf%lf%d%d",&tree[i].x,&tree[i].y,&tree[i].d,&tree[i].fa[0]);
        //其实尺寸就相当于深度
        tree[tree[i].fa[0]].son[++tree[tree[i].fa[0]].sn]=i;//记录儿子
        add(tree[i].fa[0],i);//加边
    }
    for(int i=2;i<=m;i++){
        tree[tree[i].fa[0]].snn++;
        if(tree[i].x==tree[tree[i].fa[0]].x){
            if(tree[i].y>tree[tree[i].fa[0]].y)
                tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=pi/2;
            else tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=3*pi/2;
        }
        else{
            if(tree[i].x>tree[tree[i].fa[0]].x&&
                tree[i].y>=tree[tree[i].fa[0]].y)
                tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
                atan((tree[i].y-tree[tree[i].fa[0]].y)/
                         (tree[i].x-tree[tree[i].fa[0]].x));
            if(tree[i].x<tree[tree[i].fa[0]].x&&
                tree[i].y>=tree[tree[i].fa[0]].y)
                tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
                pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/
                                (tree[i].x-tree[tree[i].fa[0]].x));
            if(tree[i].x<tree[tree[i].fa[0]].x&&
                tree[i].y<tree[tree[i].fa[0]].y)
                tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
                pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/
                                (tree[i].x-tree[tree[i].fa[0]].x));
            if(tree[i].x>tree[tree[i].fa[0]].x&&
                tree[i].y<tree[tree[i].fa[0]].y)
                tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
                2*pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/
                                    (tree[i].x-tree[tree[i].fa[0]].x));
        }//分四个区域和平行于x轴的两种情况讨论幅角
    }//求出sonf
    for(int i=1;i<=m;i++)
        for(int j=1;j<=tree[i].sn;j++){
            if(tree[i].x==tree[tree[i].son[j]].x){
                if(tree[i].y>tree[tree[i].son[j]].y)tree[tree[i].son[j]].faf=pi/2;
                else tree[tree[i].son[j]].faf=3*pi/2;
            }
            else{
                if(tree[i].x>tree[tree[i].son[j]].x&&
                    tree[i].y>=tree[tree[i].son[j]].y)
                    tree[tree[i].son[j]].faf=
                    atan((tree[i].y-tree[tree[i].son[j]].y)/
                             (tree[i].x-tree[tree[i].son[j]].x));
                if(tree[i].x<tree[tree[i].son[j]].x&&
                    tree[i].y>=tree[tree[i].son[j]].y)
                    tree[tree[i].son[j]].faf=
                    pi+atan((tree[i].y-tree[tree[i].son[j]].y)/
                                    (tree[i].x-tree[tree[i].son[j]].x));
                if(tree[i].x<tree[tree[i].son[j]].x&&
                    tree[i].y<tree[tree[i].son[j]].y)
                    tree[tree[i].son[j]].faf=
                    pi+atan((tree[i].y-tree[tree[i].son[j]].y)/
                                    (tree[i].x-tree[tree[i].son[j]].x));
                if(tree[i].x>tree[tree[i].son[j]].x&&
                     tree[i].y<tree[tree[i].son[j]].y)
                    tree[tree[i].son[j]].faf=
                    2*pi+atan((tree[i].y-tree[tree[i].son[j]].y)/
                            (tree[i].x-tree[tree[i].son[j]].x));
            }//分四个区域和平行于x轴的两种情况讨论幅角
    }//求出faf
    dfs(s);//倍增
    for(int i=1;i<=tree[1].sn;i++)
        dfs2(tree[1].son[i]);//求出标准方向上的距离
    while(t--){
        int x,y,xxx,yyy;
        double ans,xx,yy,xf,yf,xh,yh,xxxx,yyyy,hh;
        scanf("%d%lf%d%lf",&x,&xf,&y,&yf);
        if(x==y){
            printf("%.0lf\n",min(fabs(xf-yf),2*pi-fabs(xf-yf))*r[tree[x].d]/pi);
            continue;
        }//在同一圆上的情况
        int h=lca(x,y);//求LCA
        if(h==-1){
            ans=0;
            if(tree[x].d>tree[y].d)
                swap(x,y),swap(xf,yf);
            int kk;
            for(int i=1;i<=tree[x].sn;i++)
                if(lca(tree[x].son[i],y)==-1)kk=i;
            if(tree[x].d%2==0)ans+=dist(tree[x].d,tree[x].sonf[kk],xf);
            else ans+=dist(tree[x].d,xf,tree[x].sonf[kk]);
            if(tree[y].d%2==0)ans+=dist(tree[y].d,yf,tree[y].faf);
            else ans+=dist(tree[y].d,tree[y].faf,yf);
            ans+=tree[y].wtcl;
            ans-=tree[tree[x].son[kk]].wtcl;
            if(ans>pi*(ee[tree[y].d]-ee[tree[x].d]+r[tree[x].d]))
                ans=2*pi*(ee[tree[y].d]-ee[tree[x].d]+r[tree[x].d])-ans;
            printf("%.0lf\n",ans/pi);
            continue;
        }//“直系血亲”的情况
        for(int i=1;i<=tree[h].sn;i++){
            if(lca(tree[h].son[i],x)==-1)xxx=tree[h].son[i],
            xxxx=tree[h].sonf[i];
            if(lca(tree[h].son[i],y)==-1)yyy=tree[h].son[i],
            yyyy=tree[h].sonf[i];
        }
        if(tree[x].d%2==0)xx=dist(tree[x].d,xf,tree[x].faf);
        else xx=dist(tree[x].d,tree[x].faf,xf);
        if(tree[y].d%2==0)yy=dist(tree[y].d,tree[y].faf,yf);
        else yy=dist(tree[y].d,yf,tree[y].faf);
        xh=tree[x].wtcl-tree[xxx].wtcl;
        yh=2*pi*(ee[tree[y].d-1]-ee[tree[h].d])-(tree[y].wtcl-tree[yyy].wtcl);
        if(tree[h].d%2==0)hh=dist(tree[h].d,xxxx,yyyy);
        else hh=dist(tree[h].d,yyyy,xxxx);
        ans=xh+yh+xx+yy+hh;
        //分五段求和
        if
            (ans>pi*(ee[tree[x].d]+ee[tree[y].d]-ee[tree[h].d]-ee[tree[h].d-1]))
            ans=2*pi*(ee[tree[x].d]+ee[tree[y].d]-ee[tree[h].d]-ee[tree[h].d-1])-ans;
        //最后再比较大小
        printf("%.0lf\n",ans/pi);//输出
    }
    return 0;
}

0

real_hdsy_gyz LV 10 @ 2022-02-27 16:03:15

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Sunnypig闯穿梭关 /
题解
31 条题解
0
real_hdsy_gyz LV 0
发表您的题解
1

孙鹤鸣 (sunheming) LV 10 @ 1 年前
思路一：朴素想法，在所有切点间暴力建边对于每一个询问顺时针逆时针交替搜索。

时间复杂度：O(玄学)O(玄学)
思路二：不难发现此题的每组询问之间有且仅有两条路径，
且这两条路径之和为路径上所有经过的圆的周长之和。

于是想到求出任意一条路径
，然后使用路径上所有经过的圆的周长之和减去这条路径的长度得到另一条路径长度，再比较大小。

将每个圆看作一个点，两圆相切则连边，不难看出这是一棵树。

将最大的圆代表的点看做根节点，
则其实一条路径上所有经过的圆就是这两个点的LCA所经过的点代表的圆，
所以我们可以通过LCA求路径的方式快速求出使用路径上所有经过的圆的周长之和。

然后再进一步，
其实两点间路径也可以通过类似的方式
（比如定义一个标准方向，即在深度为偶数的圆上顺时针走，
深度为奇数的圆上顺时针走）。

然后就可以发现其实一条路径可以分为五部分，
即在询问中一个给定的节点（圆）由给定幅角到与它父亲节点（圆）的切点按照标准方向走的路径、
这个给定的节点（圆）与它父亲节点（圆）的切点到给定的两个节点的LCA（圆）按照标准方向走的路径、
在给定的两个节点的LCA（圆）上按照标准方向走的路径，
另一个给定的节点（圆）与它父亲节点（圆）的切点到给定的两个节点的LCA（圆）按照逆标准方向走的路径、
这个给定的节点（圆）由给定幅角到与它父亲节点（圆）的切点按照逆标准方向走的路径。

可能上一段看起来有点冗长，则咱们来看点直观的：

箭头代表这个圆的标准方向，则从AA点到BB点的路径可以分为五段，即红段、橙段、黄段、绿段（你没看错那就是一个点），蓝段。

然后得到答案就很简单啦。

但是注意还有两种情况，即一个圆是另一个圆父亲的情况或在同一圆上的情况，需单独考虑，由于比较简单，留给读者自己思考~~其实是我懒。~~

下面上我冗长的代码（含注释）

#include<bits/stdc++.h>
using namespace std;
const double pi=3.14159265358979323846;
int nex[6005],beg[6005],to[6005],r[3005],n,m,t,e,s,ee[3005];
struct T{
double x,y,sonf[15],faf,wtcl;
int d,fa[25],sn,snn,son[15];
}tree[3005];//定义节点，sonf、faf为儿子节点（圆）、父亲节点（圆）的幅角
void add(int x,int y){
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}//链式前向星
double dist(int d,double x,double y){
if(x>y)return (2*pi-x+y)*r[d];
return (y-x)*r[d];
}//计算两点在尺寸为d的圆上逆时针距离
void dfs(int s){
for(int i=1;(1<<i)<=tree[s].d;i++)
tree[s].fa[i]=tree[tree[s].fa[i-1]].fa[i-1];
for(int i=beg[s];i;i=nex[i])dfs(to[i]);
}//倍增预处理
void dfs2(int s){
for(int i=1;i<=tree[s].sn;i++)
if(tree[s].d%2==0){
tree[tree[s].son[i]].wtcl=
tree[s].wtcl+dist(tree[s].d,tree[s].sonf[i],tree[s].faf);
dfs2(tree[s].son[i]);
}
else {
tree[tree[s].son[i]].wtcl=
tree[s].wtcl+dist(tree[s].d,tree[s].faf,tree[s].sonf[i]);
dfs2(tree[s].son[i]);
}
}//标准方向的距离预处理
int lca(int a,int b){
if(tree[a].d>tree[b].d)
swap(a,b);
for(int i=20;i>=0;i--)
if(tree[a].d+(1<<i)<=tree[b].d)
b=tree[b].fa[i];
if(a==b)return -1;
for(int i=20;i>=0;i--)
if(tree[a].fa[i]!=tree[b].fa[i]){
a=tree[a].fa[i];
b=tree[b].fa[i];
}
return tree[a].fa[0];
}//LCA
int main(){
scanf("%d%d%d",&n,&m,&t);
r[0]=1e5;
ee[0]=1e5;//ee是r的前缀和
for(int i=1;i<=n;i++)
scanf("%d",&r[i]),ee[i]=ee[i-1]+r[i];
s=1;//根节点为1
for(int i=1;i<=m;i++){
scanf("%lf%lf%d%d",&tree[i].x,&tree[i].y,&tree[i].d,&tree[i].fa[0]);
//其实尺寸就相当于深度
tree[tree[i].fa[0]].son[++tree[tree[i].fa[0]].sn]=i;//记录儿子
add(tree[i].fa[0],i);//加边
}
for(int i=2;i<=m;i++){
tree[tree[i].fa[0]].snn++;
if(tree[i].x==tree[tree[i].fa[0]].x){
if(tree[i].y>tree[tree[i].fa[0]].y)
tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=pi/2;
else tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=3*pi/2;
}
else{
if(tree[i].x>tree[tree[i].fa[0]].x&&
tree[i].y>=tree[tree[i].fa[0]].y)
tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
atan((tree[i].y-tree[tree[i].fa[0]].y)/
(tree[i].x-tree[tree[i].fa[0]].x));
if(tree[i].x<tree[tree[i].fa[0]].x&&
tree[i].y>=tree[tree[i].fa[0]].y)
tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/
(tree[i].x-tree[tree[i].fa[0]].x));
if(tree[i].x<tree[tree[i].fa[0]].x&&
tree[i].y<tree[tree[i].fa[0]].y)
tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/
(tree[i].x-tree[tree[i].fa[0]].x));
if(tree[i].x>tree[tree[i].fa[0]].x&&
tree[i].y<tree[tree[i].fa[0]].y)
tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
2*pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/
(tree[i].x-tree[tree[i].fa[0]].x));
}//分四个区域和平行于x轴的两种情况讨论幅角
}//求出sonf
for(int i=1;i<=m;i++)
for(int j=1;j<=tree[i].sn;j++){
if(tree[i].x==tree[tree[i].son[j]].x){
if(tree[i].y>tree[tree[i].son[j]].y)tree[tree[i].son[j]].faf=pi/2;
else tree[tree[i].son[j]].faf=3*pi/2;
}
else{
if(tree[i].x>tree[tree[i].son[j]].x&&
tree[i].y>=tree[tree[i].son[j]].y)
tree[tree[i].son[j]].faf=
atan((tree[i].y-tree[tree[i].son[j]].y)/
(tree[i].x-tree[tree[i].son[j]].x));
if(tree[i].x<tree[tree[i].son[j]].x&&
tree[i].y>=tree[tree[i].son[j]].y)
tree[tree[i].son[j]].faf=
pi+atan((tree[i].y-tree[tree[i].son[j]].y)/
(tree[i].x-tree[tree[i].son[j]].x));
if(tree[i].x<tree[tree[i].son[j]].x&&
tree[i].y<tree[tree[i].son[j]].y)
tree[tree[i].son[j]].faf=
pi+atan((tree[i].y-tree[tree[i].son[j]].y)/
(tree[i].x-tree[tree[i].son[j]].x));
if(tree[i].x>tree[tree[i].son[j]].x&&
tree[i].y<tree[tree[i].son[j]].y)
tree[tree[i].son[j]].faf=
2*pi+atan((tree[i].y-tree[tree[i].son[j]].y)/
(tree[i].x-tree[tree[i].son[j]].x));
}//分四个区域和平行于x轴的两种情况讨论幅角
}//求出faf
dfs(s);//倍增
for(int i=1;i<=tree[1].sn;i++)
dfs2(tree[1].son[i]);//求出标准方向上的距离
while(t--){
int x,y,xxx,yyy;
double ans,xx,yy,xf,yf,xh,yh,xxxx,yyyy,hh;
scanf("%d%lf%d%lf",&x,&xf,&y,&yf);
if(x==y){
printf("%.0lf\n",min(fabs(xf-yf),2*pi-fabs(xf-yf))*r[tree[x].d]/pi);
continue;
}//在同一圆上的情况
int h=lca(x,y);//求LCA
if(h==-1){
ans=0;
if(tree[x].d>tree[y].d)
swap(x,y),swap(xf,yf);
int kk;
for(int i=1;i<=tree[x].sn;i++)
if(lca(tree[x].son[i],y)==-1)kk=i;
if(tree[x].d%2==0)ans+=dist(tree[x].d,tree[x].sonf[kk],xf);
else ans+=dist(tree[x].d,xf,tree[x].sonf[kk]);
if(tree[y].d%2==0)ans+=dist(tree[y].d,yf,tree[y].faf);
else ans+=dist(tree[y].d,tree[y].faf,yf);
ans+=tree[y].wtcl;
ans-=tree[tree[x].son[kk]].wtcl;
if(ans>pi*(ee[tree[y].d]-ee[tree[x].d]+r[tree[x].d]))
ans=2*pi*(ee[tree[y].d]-ee[tree[x].d]+r[tree[x].d])-ans;
printf("%.0lf\n",ans/pi);
continue;
}//“直系血亲”的情况
for(int i=1;i<=tree[h].sn;i++){
if(lca(tree[h].son[i],x)==-1)xxx=tree[h].son[i],
xxxx=tree[h].sonf[i];
if(lca(tree[h].son[i],y)==-1)yyy=tree[h].son[i],
yyyy=tree[h].sonf[i];
}
if(tree[x].d%2==0)xx=dist(tree[x].d,xf,tree[x].faf);
else xx=dist(tree[x].d,tree[x].faf,xf);
if(tree[y].d%2==0)yy=dist(tree[y].d,tree[y].faf,yf);
else yy=dist(tree[y].d,yf,tree[y].faf);
xh=tree[x].wtcl-tree[xxx].wtcl;
yh=2*pi*(ee[tree[y].d-1]-ee[tree[h].d])-(tree[y].wtcl-tree[yyy].wtcl);
if(tree[h].d%2==0)hh=dist(tree[h].d,xxxx,yyyy);
else hh=dist(tree[h].d,yyyy,xxxx);
ans=xh+yh+xx+yy+hh;
//分五段求和
if
(ans>pi*(ee[tree[x].d]+ee[tree[y].d]-ee[tree[h].d]-ee[tree[h].d-1]))
ans=2*pi*(ee[tree[x].d]+ee[tree[y].d]-ee[tree[h].d]-ee[tree[h].d-1])-ans;
//最后再比较大小
printf("%.0lf\n",ans/pi);//输出
}
return 0;
}
Copy
0

mike_nzk LV 10 @ 12 年前
Accepted 有效得分：100 有效耗时：222ms（时间很2）

一个沙茶错误调了好久啊...

顺便OTL一下LX

0

ufo172849z LV 10 @ 12 年前
半个星期的成果啊！

先是在处理光滑路径上出了问题，卡了好久好久。

处理完计算几何问题以后，本来以为只要线段树就可以的，但是发现TLE了。又只好改成ST表来做。

其实这个题目就是考验耐心。。。8.46KB的程序，能称的上算法的只有ST表了。

0

asd369zhu4 LV 9 @ 13 年前
哪个BT出的题，站出来，小心我夺走你的初吻！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

-1

alexshan LV 8 @ 6 年前
cout<<i<<endl;

-1

Silence•轩辕•寂 LV 10 @ 7 年前
不明觉厉~

-1

刘幽 LV 6 @ 9 年前
Const maxn=1000100;

Var

sa,sb,se,a,b,e,f,q:array[1..maxn*2]of int64;

vis:array[1..maxn*2]of boolean;

dis:array[1..maxn*2]of int64;

n,m,k,i,j:longint;

sum:qword;

Procedure init;

var i:longint;

begin

readln(n,m);

for i:=1 to m do readln(sa[i],sb[i],se[i]);

end;

Procedure qsort(l,r:longint);

var i,j,x,y:longint;

begin

i:=l;j:=r;x:=a[(l+r)shr 1];

Repeat

while a[i]x do dec(j);

if ij;

if idis+cost1[k] then begin

dis[toti1[k]]:=dis+cost1[k];

if not check[toti1[k]] then begin

inc(tail);

team[tail]:=toti1[k];

check[toti1[k]]:=true;

end;

k:=next1[k];

end;

until head>tail;

for i:=1 to p do inc(ans,dis[i]);

end;

procedure spfa2;

var

i,head,tail,k,u:longint;

begin

fillchar(check,sizeof(check),false);

for i:=1 to p do dis[i]:=30000000001;

head:=0;

tail:=1;

dis[1]:=0;

team[1]:=1;

check[1]:=true;

repeat

inc(head);

u:=team[head];

check:=false;

k:=list2;

while k0 do begin

if dis[toti2[k]]>dis+cost2[k] then begin

dis[toti2[k]]:=dis+cost2[k];

if not check[toti2[k]] then begin

inc(tail);

team[tail]:=toti2[k];

check[toti2[k]]:=true;

end;

k:=next2[k];

end;

until head>tail;

for i:=1 to p do inc(ans,dis[i]);

end;

begin

assign(input,'poj1511.in');

reset(input);

readln(nn);

for ii:=1 to nn do begin

readln(p,q);

ans:=0;

tot:=0;

fillchar(list1,sizeof(list1),0);

fillchar(list2,sizeof(list2),0);

for i:=1 to q do begin

readln(x,y,z);

add1(x,y,z);

add2(y,x,z);

end;

spfa1;

spfa2;

writeln(ans);

end;

close(input);

end.

Const maxn=1000100;

Var

sa，sb，se，a，b，e，f，q:array[1..maxn*2]of int64;

vis:array[1..maxn*2]of boolean;

dis:array[1..maxn*2]of int64;

n，m，k，i，j:longint;

sum:qword;

Procedure init;

var i:longint;

begin

readln（n，m）;

for i:=1 to m do readln（sa[i]，sb[i]，se[i]）;

end;

Procedure qsort（l，r:longint）;

var i，j，x，y:longint;

begin

i:=l;j:=r;x:=a[（l+r）shr 1];

Repeat

while a[i]x do dec（j）;

if ij;

if i

-1

新建文件夹 LV 10 @ 9 年前
终于知道这题为什么过的人那么少的原因了

xocoder @ 5 年前
这题就是要有耐心，不难。奥数题比这些难多了。赞一下过的人！

-1

a798443952 LV 4 @ 12 年前
这个我做出来了想知道题解+QQ358736331

-1

黄望宁 LV 9 @ 12 年前
记录编号 Flag 得分记录信息环境评测机程序提交时间

R1545636 Unaccepted 7 From zybbsoi－

　P1086 FPC Vivid Puppy 2009-9-19 23:17:51

R1441512 No Compiled 0 From lyyqy0910－

　P1086 GCC Vijos Sunny 2009-8-17 20:38:14

R1387666 Unaccepted 0 From -AI-－

　P1086 FPC Vivid Puppy 2009-8-5 14:45:40

R1373404 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-8-1 14:52:19

R1355379 Unaccepted 0 From Ck0123－

　P1086 FPC Vivid Puppy 2009-7-26 20:28:23

R1315961 No Compiled 0 From qazx－

　P1086 FPC Vivid Puppy 2009-7-15 13:53:54

R1315954 Unaccepted 0 From qazx－

　P1086 FPC Vivid Puppy 2009-7-15 13:52:52

R1315930 Unaccepted 0 From qazx－

　P1086 FPC Vivid Puppy 2009-7-15 13:48:30

R1248466 No Compiled 0 From 王者v归来－

　P1086 FPC Vivid Puppy 2009-5-23 20:10:31

R1248461 No Compiled 0 From 王者v归来－

　P1086 FPC Vivid Puppy 2009-5-23 20:09:10

R1230617 Unaccepted 56 From banduoxian－

　P1086 FPC Vivid Puppy 2009-5-6 18:07:46

R1230556 Unaccepted 0 From banduoxian－

　P1086 FPC Vag 6K 2009-5-6 17:38:37

R1230555 Unaccepted 0 From banduoxian－

　P1086 FPC Vivid Puppy 2009-5-6 17:37:42

R1228743 No Compiled 0 From zzq401390508－

　P1086 GCC Vivid Puppy 2009-5-4 19:32:48

R1226554 No Compiled 0 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 16:06:19

R1226528 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 15:45:13

R1226355 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 12:51:59

R1226304 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 11:54:49

R1226295 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 11:48:52

R1226261 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 11:33:38

R1226242 No Compiled 0 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 11:24:16

-1

hjjqq LV 4 @ 12 年前
xcvdc

-1

Ck0123 LV 9 @ 12 年前
{信春哥,得永生}

-1

董 LV 10 @ 12 年前
& &

—

-1

LV 0 @ 12 年前
我只做难度六的题，这种题。。。还是留我徒弟做吧

-1

ZXOO LV 8 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

-1

cbtcs LV 3 @ 13 年前
记录编号 Flag 得分记录信息环境评测机程序提交时间

R1001133 Unaccepted 85 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-4 17:56:39

R1001125 Unaccepted 59 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-4 17:55:08

R1001115 Unaccepted 56 From Cowboy80－

　P1086 FPC Vag 6K 2008-11-4 17:54:00

R998515 Accepted 100 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 22:15:54

R998511 Unaccepted 56 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 22:14:38

R998490 Unaccepted 56 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 22:10:21

R998293 Unaccepted 7 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 21:39:22

R998165 Unaccepted 7 From Cowboy80－

　P1086 FPC Vijos Dragon 2008-11-3 21:26:09

R998008 Unaccepted 0 From Cowboy80－

　P1086 FPC Vijos Dragon 2008-11-3 21:08:21

R997701 Unaccepted 0 From Cowboy80－

　P1086 FPC Vijos Dragon 2008-11-3 20:34:51

R997634 Unaccepted 0 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 20:27:46

R997565 Unaccepted 0 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 20:20:02

R997232 Unaccepted 0 From Cowboy80－

　P1086 FPC Vijos Dragon 2008-11-3 19:41:23

R997213 No Compiled 0 From Cowboy80－

　你牛，一下。

拽可以，但要务实。

-1

Cowboy80 LV 8 @ 12 年前
update in June, 2009:

回复cbtcs：

虽然看起来我好象从开始交到AC用了一天。但是看清楚，我11-3号已经过了，后面只是优化代码而已！而且我们学校不像你们的，我们没有停课集训，那一天只是利用晚上晚自习的时间做而已！！

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

难度为5，通过6人，通过率1/50的题目也不过如此嘛……就这样一下子就被我ac了。

不过就是LCA+树的遍历+节点标号+RMQ+两个ST表+动态规划+记忆化搜索+位运算+计算几何+三角函数+反三角函数而已嘛…………

Easy_dla. Pass!

-1

su6422 LV 8 @ 13 年前
恐怖...

-1

w122185976q LV 9 @ 13 年前
在是人做的题吗?超BT啊!!!!!!!!!!!!

-1

FancyMouse LV 3 @ 14 年前
LCA...偶的算法目前ok，只是要用80mb内存……哎，可恶的mle……

1 2 下一页 › 末页 »
Sunnypig闯穿梭关
查看题目
递交
讨论
题解
信息
ID1086递交 Accepted难度8分类点击显示标签
Sunnypig的奇幻之旅省选 2005 湖南
递交数478我的递交数1已通过37通过率8%被复制4上传者 chp516
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

mike_nzk LV 10 @ 2009-11-07 16:34:26

Accepted 有效得分：100 有效耗时：222ms（时间很2）

一个沙茶错误调了好久啊...

顺便OTL一下LX

0

ufo172849z LV 10 @ 2009-11-05 20:15:06

半个星期的成果啊！

先是在处理光滑路径上出了问题，卡了好久好久。

处理完计算几何问题以后，本来以为只要线段树就可以的，但是发现TLE了。又只好改成ST表来做。

其实这个题目就是考验耐心。。。8.46KB的程序，能称的上算法的只有ST表了。

0

asd369zhu4 LV 9 @ 2009-02-21 20:29:51

哪个BT出的题，站出来，小心我夺走你的初吻！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

-1

神-董 (董由) LV 7 @ 2022-07-16 22:29:55

\(\rule{10000000mm}{100000000mm}\)

-1

alexshan LV 8 @ 2015-09-20 21:10:02

cout<<i<<endl;

-1

Silence•轩辕•寂 LV 10 @ 2014-09-08 11:41:07

不明觉厉~

-1

刘幽 LV 6 @ 2012-08-19 17:21:36

Const maxn=1000100;

Var

sa,sb,se,a,b,e,f,q:array[1..maxn*2]of int64;

vis:array[1..maxn*2]of boolean;

dis:array[1..maxn*2]of int64;

n,m,k,i,j:longint;

sum:qword;

Procedure init;

var i:longint;

begin

readln(n,m);

for i:=1 to m do readln(sa[i],sb[i],se[i]);

end;

Procedure qsort(l,r:longint);

var i,j,x,y:longint;

begin

i:=l;j:=r;x:=a[(l+r)shr 1];

Repeat

while a[i]x do dec(j);

if ij;

if idis+cost1[k] then begin

dis[toti1[k]]:=dis+cost1[k];

if not check[toti1[k]] then begin

inc(tail);

team[tail]:=toti1[k];

check[toti1[k]]:=true;

end;

end;

k:=next1[k];

end;

until head>tail;

for i:=1 to p do inc(ans,dis[i]);

end;

procedure spfa2;

var

i,head,tail,k,u:longint;

begin

fillchar(check,sizeof(check),false);

for i:=1 to p do dis[i]:=30000000001;

head:=0;

tail:=1;

dis[1]:=0;

team[1]:=1;

check[1]:=true;

repeat

inc(head);

u:=team[head];

check:=false;

k:=list2;

while k0 do begin

if dis[toti2[k]]>dis+cost2[k] then begin

dis[toti2[k]]:=dis+cost2[k];

if not check[toti2[k]] then begin

inc(tail);

team[tail]:=toti2[k];

check[toti2[k]]:=true;

end;

end;

k:=next2[k];

end;

until head>tail;

for i:=1 to p do inc(ans,dis[i]);

end;

begin

assign(input,'poj1511.in');

reset(input);

readln(nn);

for ii:=1 to nn do begin

readln(p,q);

ans:=0;

tot:=0;

fillchar(list1,sizeof(list1),0);

fillchar(list2,sizeof(list2),0);

for i:=1 to q do begin

readln(x,y,z);

add1(x,y,z);

add2(y,x,z);

end;

spfa1;

spfa2;

writeln(ans);

end;

close(input);

end.

Const maxn=1000100;

Var

sa，sb，se，a，b，e，f，q:array[1..maxn*2]of int64;

vis:array[1..maxn*2]of boolean;

dis:array[1..maxn*2]of int64;

n，m，k，i，j:longint;

sum:qword;

Procedure init;

var i:longint;

begin

readln（n，m）;

for i:=1 to m do readln（sa[i]，sb[i]，se[i]）;

end;

Procedure qsort（l，r:longint）;

var i，j，x，y:longint;

begin

i:=l;j:=r;x:=a[（l+r）shr 1];

Repeat

while a[i]x do dec（j）;

if ij;

if i

-1

新建文件夹 LV 10 @ 2012-07-20 19:45:27

终于知道这题为什么过的人那么少的原因了

xocoder @ 2016-10-06 18:54:55

这题就是要有耐心，不难。奥数题比这些难多了。赞一下过的人！

-1

a798443952 LV 4 @ 2009-10-26 20:17:25

这个我做出来了想知道题解+QQ358736331

-1

黄望宁 LV 9 @ 2009-09-22 19:41:05

记录编号 Flag 得分记录信息环境评测机程序提交时间

R1545636 Unaccepted 7 From zybbsoi－

　P1086 FPC Vivid Puppy 2009-9-19 23:17:51

R1441512 No Compiled 0 From lyyqy0910－

　P1086 GCC Vijos Sunny 2009-8-17 20:38:14

R1387666 Unaccepted 0 From -AI-－

　P1086 FPC Vivid Puppy 2009-8-5 14:45:40

R1373404 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-8-1 14:52:19

R1355379 Unaccepted 0 From Ck0123－

　P1086 FPC Vivid Puppy 2009-7-26 20:28:23

R1315961 No Compiled 0 From qazx－

　P1086 FPC Vivid Puppy 2009-7-15 13:53:54

R1315954 Unaccepted 0 From qazx－

　P1086 FPC Vivid Puppy 2009-7-15 13:52:52

R1315930 Unaccepted 0 From qazx－

　P1086 FPC Vivid Puppy 2009-7-15 13:48:30

R1248466 No Compiled 0 From 王者v归来－

　P1086 FPC Vivid Puppy 2009-5-23 20:10:31

R1248461 No Compiled 0 From 王者v归来－

　P1086 FPC Vivid Puppy 2009-5-23 20:09:10

R1230617 Unaccepted 56 From banduoxian－

　P1086 FPC Vivid Puppy 2009-5-6 18:07:46

R1230556 Unaccepted 0 From banduoxian－

　P1086 FPC Vag 6K 2009-5-6 17:38:37

R1230555 Unaccepted 0 From banduoxian－

　P1086 FPC Vivid Puppy 2009-5-6 17:37:42

R1228743 No Compiled 0 From zzq401390508－

　P1086 GCC Vivid Puppy 2009-5-4 19:32:48

R1226554 No Compiled 0 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 16:06:19

R1226528 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 15:45:13

R1226355 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 12:51:59

R1226304 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 11:54:49

R1226295 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 11:48:52

R1226261 Unaccepted 7 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 11:33:38

R1226242 No Compiled 0 From jimistdponde－

　P1086 FPC Vivid Puppy 2009-5-2 11:24:16

-1

hjjqq LV 4 @ 2009-08-06 10:24:03

xcvdc

-1

Ck0123 LV 9 @ 2009-07-26 20:28:02

{信春哥,得永生}

-1

董 LV 10 @ 2009-07-22 22:06:12

& &

—

-1

LV 0 @ 2009-07-01 12:06:25

我只做难度六的题，这种题。。。还是留我徒弟做吧

-1

ZXOO LV 8 @ 2009-02-11 17:03:54

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

-1

cbtcs LV 3 @ 2008-11-04 23:29:18

记录编号 Flag 得分记录信息环境评测机程序提交时间

R1001133 Unaccepted 85 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-4 17:56:39

R1001125 Unaccepted 59 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-4 17:55:08

R1001115 Unaccepted 56 From Cowboy80－

　P1086 FPC Vag 6K 2008-11-4 17:54:00

R998515 Accepted 100 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 22:15:54

R998511 Unaccepted 56 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 22:14:38

R998490 Unaccepted 56 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 22:10:21

R998293 Unaccepted 7 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 21:39:22

R998165 Unaccepted 7 From Cowboy80－

　P1086 FPC Vijos Dragon 2008-11-3 21:26:09

R998008 Unaccepted 0 From Cowboy80－

　P1086 FPC Vijos Dragon 2008-11-3 21:08:21

R997701 Unaccepted 0 From Cowboy80－

　P1086 FPC Vijos Dragon 2008-11-3 20:34:51

R997634 Unaccepted 0 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 20:27:46

R997565 Unaccepted 0 From Cowboy80－

　P1086 FPC Vijos Dolphin 2008-11-3 20:20:02

R997232 Unaccepted 0 From Cowboy80－

　P1086 FPC Vijos Dragon 2008-11-3 19:41:23

R997213 No Compiled 0 From Cowboy80－

　你牛，一下。

拽可以，但要务实。

-1

Cowboy80 LV 8 @ 2009-06-17 19:57:13

update in June, 2009:

回复cbtcs：

虽然看起来我好象从开始交到AC用了一天。但是看清楚，我11-3号已经过了，后面只是优化代码而已！而且我们学校不像你们的，我们没有停课集训，那一天只是利用晚上晚自习的时间做而已！！

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

难度为5，通过6人，通过率1/50的题目也不过如此嘛……就这样一下子就被我ac了。

不过就是LCA+树的遍历+节点标号+RMQ+两个ST表+动态规划+记忆化搜索+位运算+计算几何+三角函数+反三角函数而已嘛…………

Easy_dla. Pass!

-1

su6422 LV 8 @ 2008-09-30 14:10:34

恐怖...

题解

33 条题解

Sunnypig闯穿梭关

信息

状态

开发

支持

还没有账户？

登录