2013-1019

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
解题报告：
首先，该题有一个这样的性质，在保证最优的情况下，加速次数只能是0,1,2……w，或者是无穷次。
证明如下，对于两个加速点a，b，a为距b最近的加速点，假设最优方案要经过b的话。
ab间一次来回，需要花费(3/4)*(2*d(a,b))的时间，但是速度翻了4倍，于是b到终点时间减少了3/4。

所以
1、若ab距离的两倍小于等于b到终点最短距离，则在ab间无限加速更快。
   时间收敛到ab距离的两倍除以b点在开始绕之前的速度，之后瞬间到终点(无限速度）
2、若ab距离的两倍大于b到终点的最短距离，则选择不绕，直接走向终点。

具体做法：
1、对于无穷的处理：首先我们对全图做一次floyd，加速点不作为中间节点。就能求出加速点之间的距离（普通点可以忽略）。
   然后对于每一个加速点i，找到一个与他最近的加速点，距离存为d[i]。
2、分层图SPFA：将每个点按加速次数分成若干个点（加速0次，1次……w次），然后正向做一次SPFA，求出每个点在每个加速次数下的最小到达时间。
3、算出到终点的最小时间以及加速次数：对于每个加速点，判断一下是直接到终点快还是无限加速(2*d[i]/v)到终点快，在这个基础下再得出最大加速次数。

可以注意到，当加速次数超过57次的话，已经超越的double的精度，而SPFA中需要处理的加速次数最高为99次。
所以我们不能用double来存储最小时间，而是用3个long long来存储，这样精度就能达到小数点后120位，可以精确地算出到达每个点的时间。

}}}

{{{
Code：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MN=101,MX=1000001;
long long e[64];
struct dg100 { long long p[3]; } t[MN][MN];
int f[MN][MN],a[MN],p[MN],d[MN];
int n,m,w;
//f->edge;
//a->acceleration point;
//p[i]->weather vertex i is acceleration point;
//d[i]->the shortest distance between two acceleration point;
//t[i][j]->the time to reach vertex i with j times acceleration;
//e[i]=2^i;

void init(){
    int i,x,y,z;
    memset(f,1,sizeof(f));
    for (i=1; i<=m; i++){
        scanf("%d%d%d",&x,&y,&z);
        if (f[x][y]>z){ f[x][y]=z; f[y][x]=z; }
    }
    memset(p,0,sizeof(p));
    memset(a,0,sizeof(a));
    a[0]=w;
    for (i=1; i<=a[0]; i++){
        scanf("%d",&x);
        p[x]=1; a[i]=x;
    }
}

void floyd(){
    int i,j,k;
    for (k=1; k<=n; k++) if (!p[k])
        for (i=1; i<=n; i++) if (i!=k)
            for (j=i+1; j<=n; j++)
                if (f[i][k]+f[k][j]<f[i][j]) {
                    f[i][j]=f[i][k]+f[k][j];
                    f[j][i]=f[i][j];
                }
    memset(d,1,sizeof(d));
    for (i=1; i<=a[0]; i++)
        for (j=1; j<=a[0]; j++) if (i!=j)
            if (f[a[i]][a[j]]<d[a[i]]) d[a[i]]=f[a[i]][a[j]];
}

dg100 time(int a,int v){
    dg100 k;
    k.p[0]=0; k.p[1]=0; k.p[2]=0;
    int i=v/60,j;
    v=v%60;
    k.p[i]=a/e[v];
    k.p[i+1]=a%e[v]*e[60-v];
    return k;
}

void add(dg100* a,dg100 x,dg100 y){
    a->p[2]=x.p[2]+y.p[2];
    a->p[1]=x.p[1]+y.p[1]+a->p[2]/e[60];
    a->p[2]=a->p[2]%e[60];
    a->p[0]=x.p[0]+y.p[0]+a->p[1]/e[60];
    a->p[1]=a->p[1]%e[60];
}

int cmp(dg100 a,dg100 b){
    int i;
    for (i=0; i<3; i++)
        if (a.p[i]<b.p[i]) return -1;
        else if(a.p[i]>b.p[i]) return 1;
    return 0;
}

int ass(dg100* a,dg100 b){
    a->p[0]=b.p[0];
    a->p[1]=b.p[1];
    a->p[2]=b.p[2];
}

void dp(){
    int i,j,k;
    for (i=1; i<=n; i++)
        for (j=0; j<=n; j++) t[i][j].p[0]=MX;
    for (k=0; k<3; k++)
        t[1][p[1]].p[k]=0;
    dg100 temp;
    int v=p[1],x=1,y;
    for (j=1; j<=a[0]; j++){
        y=a[j];
        if (f[x][y]>=MX) continue;
        add(&temp,t[x][v],time(f[x][y],v));
        if (cmp(temp,t[y][v+1])==-1) ass(&t[y][v+1],temp);
    }
    for (v=p[1]+1; v<a[0]; v++)
        for (i=1; i<=a[0]; i++){
            x=a[i];
            if (t[x][v].p[0]>=MX) continue;
            for (j=1; j<=a[0]; j++){
                y=a[j];
                if (f[x][y]>=MX) continue;
                add(&temp,t[x][v],time(f[x][y],v));
                if (cmp(temp,t[y][v+1])==-1) ass(&t[y][v+1],temp);
            }
        }
}

void writeit(){
    dg100 ans,temp;
    ans.p[0]=f[1][n]; ans.p[1]=0; ans.p[2]=0;
    int i,j,k,v=p[1],flag;
    f[n][n]=0;
    for (i=1; i<=a[0]; i++)
        for (j=1; j<=a[0]; j++){
            k=a[i];
            add(&temp,t[k][j],time(f[k][n],j));
            flag=cmp(temp,ans);
            if (flag==-1 || flag==0 && j>v) { ass(&ans,temp); v=j; }
            add(&temp,t[k][j],time(d[k]*2,j));
            flag=cmp(temp,ans);
            if (flag!=1) { ass(&ans,temp); v=MX; }
        }
    double a=ans.p[0],b=ans.p[1],c=ans.p[2];
    b=b/e[60]; c=c/e[60]/e[60];
    a=a+b+c;
    printf("%.6f ",a);
    if (v>=MX) printf("Burst Evolution!\n"); else printf("%d\n",v);
}

int main(){
    e[0]=1;
    for (int i=1; i<=61; i++) e[i]=e[i-1]*2;
    while (scanf("%d%d%d",&n,&m,&w)!=EOF){
        init();
        floyd();
        dp();
        writeit();
    }
    return 0;
}
}}}

解题报告：
首先，该题有一个这样的性质，在保证最优的情况下，加速次数只能是0,1,2……w，或者是无穷次。
证明如下，对于两个加速点a，b，a为距b最近的加速点，假设最优方案要经过b的话。
ab间一次来回，需要花费(3/4)*(2*d(a,b))的时间，但是速度翻了4倍，于是b到终点时间减少了3/4。
所以
1、若ab距离的两倍小于等于b到终点最短距离，则在ab间无限加速更快。
   时间收敛到ab距离的两倍除以b点在开始绕之前的速度，之后瞬间到终点(无限速度）
2、若ab距离的两倍大于b到终点的最短距离，则选择不绕，直接走向终点。
具体做法：
1、对于无穷的处理：首先我们对全图做一次floyd，加速点不作为中间节点。就能求出加速点之间的距离（普通点可以忽略）。
   然后对于每一个加速点i，找到一个与他最近的加速点，距离存为d[i]。
2、分层图SPFA：将每个点按加速次数分成若干个点（加速0次，1次……w次），然后正向做一次SPFA，求出每个点在每个加速次数下的最小到达时间。
3、算出到终点的最小时间以及加速次数：对于每个加速点，判断一下是直接到终点快还是无限加速(2*d[i]/v)到终点快，在这个基础下再得出最大加速次数。
可以注意到，当加速次数超过57次的话，已经超越的double的精度，而SPFA中需要处理的加速次数最高为99次。
所以我们不能用double来存储最小时间，而是用3个long long来存储，这样精度就能达到小数点后120位，可以精确地算出到达每个点的时间。

Code：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MN=101,MX=1000001;
long long e[64];
struct dg100 { long long p[3]; } t[MN][MN];
int f[MN][MN],a[MN],p[MN],d[MN];
int n,m,w;
//f->edge;
//a->acceleration point;
//p[i]->weather vertex i is acceleration point;
//d[i]->the shortest distance between two acceleration point;
//t[i][j]->the time to reach vertex i with j times acceleration;
//e[i]=2^i;
void init(){
    int i,x,y,z;
    memset(f,1,sizeof(f));
    for (i=1; i<=m; i++){
        scanf("%d%d%d",&x,&y,&z);
        if (f[x][y]>z){ f[x][y]=z; f[y][x]=z; }
    }
    memset(p,0,sizeof(p));
    memset(a,0,sizeof(a));
    a[0]=w;
    for (i=1; i<=a[0]; i++){
        scanf("%d",&x);
        p[x]=1; a[i]=x;
    }
}
void floyd(){
    int i,j,k;
    for (k=1; k<=n; k++) if (!p[k])
        for (i=1; i<=n; i++) if (i!=k)
            for (j=i+1; j<=n; j++)
                if (f[i][k]+f[k][j]<f[i][j]) {
                    f[i][j]=f[i][k]+f[k][j];
                    f[j][i]=f[i][j];
                }
    memset(d,1,sizeof(d));
    for (i=1; i<=a[0]; i++)
        for (j=1; j<=a[0]; j++) if (i!=j)
            if (f[a[i]][a[j]]<d[a[i]]) d[a[i]]=f[a[i]][a[j]];
}
dg100 time(int a,int v){
    dg100 k;
    k.p[0]=0; k.p[1]=0; k.p[2]=0;
    int i=v/60,j;
    v=v%60;
    k.p[i]=a/e[v];
    k.p[i+1]=a%e[v]*e[60-v];
    return k;
}
void add(dg100* a,dg100 x,dg100 y){
    a->p[2]=x.p[2]+y.p[2];
    a->p[1]=x.p[1]+y.p[1]+a->p[2]/e[60];
    a->p[2]=a->p[2]%e[60];
    a->p[0]=x.p[0]+y.p[0]+a->p[1]/e[60];
    a->p[1]=a->p[1]%e[60];
}
int cmp(dg100 a,dg100 b){
    int i;
    for (i=0; i<3; i++)
        if (a.p[i]<b.p[i]) return -1;
        else if(a.p[i]>b.p[i]) return 1;
    return 0;
}
int ass(dg100* a,dg100 b){
    a->p[0]=b.p[0];
    a->p[1]=b.p[1];
    a->p[2]=b.p[2];
}
void dp(){
    int i,j,k;
    for (i=1; i<=n; i++)
        for (j=0; j<=n; j++) t[i][j].p[0]=MX;
    for (k=0; k<3; k++)
        t[1][p[1]].p[k]=0;
    dg100 temp;
    int v=p[1],x=1,y;
    for (j=1; j<=a[0]; j++){
        y=a[j];
        if (f[x][y]>=MX) continue;
        add(&temp,t[x][v],time(f[x][y],v));
        if (cmp(temp,t[y][v+1])==-1) ass(&t[y][v+1],temp);
    }
    for (v=p[1]+1; v<a[0]; v++)
        for (i=1; i<=a[0]; i++){
            x=a[i];
            if (t[x][v].p[0]>=MX) continue;
            for (j=1; j<=a[0]; j++){
                y=a[j];
                if (f[x][y]>=MX) continue;
                add(&temp,t[x][v],time(f[x][y],v));
                if (cmp(temp,t[y][v+1])==-1) ass(&t[y][v+1],temp);
            }
        }
}
void writeit(){
    dg100 ans,temp;
    ans.p[0]=f[1][n]; ans.p[1]=0; ans.p[2]=0;
    int i,j,k,v=p[1],flag;
    f[n][n]=0;
    for (i=1; i<=a[0]; i++)
        for (j=1; j<=a[0]; j++){
            k=a[i];
            add(&temp,t[k][j],time(f[k][n],j));
            flag=cmp(temp,ans);
            if (flag==-1 || flag==0 && j>v) { ass(&ans,temp); v=j; }
            add(&temp,t[k][j],time(d[k]*2,j));
            flag=cmp(temp,ans);
            if (flag!=1) { ass(&ans,temp); v=MX; }
        }
    double a=ans.p[0],b=ans.p[1],c=ans.p[2];
    b=b/e[60]; c=c/e[60]/e[60];
    a=a+b+c;
    printf("%.6f ",a);
    if (v>=MX) printf("Burst Evolution!\n"); else printf("%d\n",v);
}
int main(){
    e[0]=1;
    for (int i=1; i<=61; i++) e[i]=e[i-1]*2;
    while (scanf("%d%d%d",&n,&m,&w)!=EOF){
        init();
        floyd();
        dp();
        writeit();
    }
    return 0;
}