JZOJ.4826 小澳的葫芦解题报告

Description

小澳最喜欢的歌曲就是《葫芦娃》。

一日表演唱歌，他尽了洪荒之力，唱响心中圣歌。

随之，小澳进入了葫芦世界。

葫芦世界有n个葫芦，标号为1~ n。n个葫芦由m条藤连接，每条藤连接了两个葫芦，这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。

小澳站在1号葫芦上（你可以认为葫芦非常大，可以承受小澳的体重），他想沿着藤爬到n号葫芦上，其中每个葫芦只经过一次。

小澳找到一条路径，使得消耗的能量与经过的葫芦数的比值最小。

Input

输入文件名为calabash.in。

输入文件第一行两个正整数n,m，分别表示葫芦的个数和藤数。

接下来m行，每行三个正整数u,v,w，描述一条藤，表示这条藤由u连向v，小澳爬过这条藤需要消耗w点能量。

Output

输出文件名为calabash.out。

一行一个实数，表示答案（绝对误差不超过 10^-3）。

Sample Input

4 6

1 2 1

2 4 6

1 3 2

3 4 4

2 3 3

1 4 8

Sample Output

2.000

【输入输出样例说明】

有4种爬法：

1->4，消耗能量8，经过2个葫芦，比值为8/2=4。

1->2->4，消耗能量1+6=7，经过3个葫芦，比值为7/3≈2.33。

1->3->4，消耗能量2+4=6，经过3个葫芦，比值为6/3=2。

1->2->3->4，消耗能量1+3+4=8，经过4个葫芦，比值为8/4=2。

所以选第三种或第四种方案，答案为2。

分析：

这道题其实是最小比例生成树。但是呢。我不知道的正解写法。于是呢，所以。用了一种奇技淫巧。因为这里是有向无环图。这个我们在这里可以用最短路的想法。spfa是个好东西。由题目可以得知。这道题其实就是想让我们求1～n所有路径里，（一条路径里）每条路的平均值最小。所以我们这里其实就是要求出每条路的最短路。。其实就是每次用多少边走下来的最短路。可能有些边数也走不到。那么把所有的这个边求出来，最后算平均值就好。

所以我们设d[i][j]是第i个点从起点走了j条边到达的最短路。visit[i][j]与前面对应。就是这样。

#include<cstdio>
#include<algorithm>
#include<string.h>
#define MAX_1 10611109567
using namespace std;
struct node{
    int v,next,val;
}edge[100010];
struct que{
    int num,step;
};
que q[100010];
int d[210][2100],visit[210][2100],cnt,head[2010];
int n,m;
void spfa()
{
    que news;
    news.step=1;news.num=1;
    memset(d,0x3f,sizeof(d));
    int heads=1,last=1;
    d[1][1]=0;
    q[heads]=news;
    while(heads<=last)
    {
        que first=q[heads];
        for(int i=head[first.num];i!=-1;i=edge[i].next)
        {
            if(d[edge[i].v][first.step+1]>d[first.num][first.step]+edge[i].val){
                d[edge[i].v][first.step+1]=d[first.num][first.step]+edge[i].val;
                if(visit[edge[i].v][first.step+1])continue;
                visit[edge[i].v][first.step+1]=1;
                que l;
                l=(que){edge[i].v,first.step+1};
                q[++last]=l;
            }
        }
        visit[first.num][first.step]=0;
        ++heads;
    }
    return ;
}
void address(int x,int y,int val)
{
    edge[++cnt].v=y;
    edge[cnt].next=head[x];
    edge[cnt].val=val;
    head[x]=cnt;
}
int main()
{
    freopen("calabash.in","r",stdin);
    freopen("calabash.out","w",stdout);
    memset(head,-1,sizeof(head));
    int x,y,val;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&val);
        address(x,y,val);
    }
    spfa();
    double ans=99999999.0;
    for(int i=2;i<=n;++i)
    {
        if(d[n][i]<MAX_1)ans=min(ans,(double)d[n][i]/i);
    }
    printf("%.3lf",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

#include<cstdio>

#include<algorithm>

#include<string.h>

#define MAX_1 10611109567

using namespace std;

struct node{

int v,next,val;

}edge[100010];

struct que{

int num,step;

};

que q[100010];

int d[210][2100],visit[210][2100],cnt,head[2010];

int n,m;

void spfa()

{

que news;

news.step=1;news.num=1;

memset(d,0x3f,sizeof(d));

int heads=1,last=1;

d[1][1]=0;

q[heads]=news;

while(heads<=last)

{

que first=q[heads];

for(int i=head[first.num];i!=-1;i=edge[i].next)

{

if(d[edge[i].v][first.step+1]>d[first.num][first.step]+edge[i].val){

d[edge[i].v][first.step+1]=d[first.num][first.step]+edge[i].val;

if(visit[edge[i].v][first.step+1])continue;

visit[edge[i].v][first.step+1]=1;

que l;

l=(que){edge[i].v,first.step+1};

q[++last]=l;

}

visit[first.num][first.step]=0;

++heads;

}

return ;

}

void address(int x,int y,int val)

{

edge[++cnt].v=y;

edge[cnt].next=head[x];

edge[cnt].val=val;

head[x]=cnt;

}

int main()

{

freopen("calabash.in","r",stdin);

freopen("calabash.out","w",stdout);

memset(head,-1,sizeof(head));

int x,y,val;

scanf("%d%d",&n,&m);

for(int i=1;i<=m;++i)

{

scanf("%d%d%d",&x,&y,&val);

address(x,y,val);

}

spfa();

double ans=99999999.0;

for(int i=2;i<=n;++i)

{

if(d[n][i]<MAX_1)ans=min(ans,(double)d[n][i]/i);

}

printf("%.3lf",ans);

fclose(stdin);

fclose(stdout);

return 0;

}

没有回路的路