洛谷 P1685 游览 题解+tip【拓扑排序】【组合数学】

作者: wjyyy 分类: 拓扑排序,组合数学,解题报告 发布时间: 2018-07-08 08:46

点击量:21

 

   有向图拓扑排序+加法/乘法原理。

 

题目描述

顺利通过了黄药师的考验,下面就可以尽情游览桃花岛了!

 

你要从桃花岛的西头开始一直玩到东头,然后在东头的码头离开。可是当你游玩了一次后,发现桃花岛的景色实在是非常的美丽!!!于是你还想乘船从桃花岛东头的码头回到西头,再玩一遍,但是桃花岛有个规矩:你可以游览无数遍,但是每次游玩的路线不能完全一样。

 

我们把桃花岛抽象成了一个图,共n个点代表路的相交处,m条边表示路,边是有向的(只能按照边的方向行走),且可能有连接相同两点的边。输入保证这个图没有环,而且从西头到东头至少存在一条路线。两条路线被认为是不同的当且仅当它们所经过的路不完全相同。

 

你的任务是:把所有不同的路线游览完一共要花多少时间?

 

输入输出格式

输入格式:

第1行为5个整数:n、m、s、t、t0,分别表示点数,边数,岛西头的编号,岛东头的编号(编号是从1到n)和你乘船从岛东头到西头一次的时间。

 

以下m行,每行3个整数:x、y、t,表示从点x到点y有一条行走耗时为t的路。

 

每一行的多个数据之间用一个空格隔开,且:2<=n<=10000; 1<=m<=50000;t<=10000;t0<=10000

 

输出格式:

假设总耗时为total,则输出total mod 10000的值(total对10000取余)。

 

输入输出样例

输入样例#1:
3 4 1 3 7
1 2 5
2 3 7
2 3 10
1 3 15
输出样例#1:
56

说明

【样例说明】

共有3条路径可以从点1到点3,分别是1-2-3,1-2-3,1-3。

 

时间计算为:(5+7)+7+(5+10)+7+(15)=56

 

题解:

   对于每个点,能到达它的方案一定是能到达指向它的点的方案之和,也就是加法原理。而每次不同路线会经过相同的边,统计前面的方案数,乘上边权,再继承(加上)所来点的总时间,就是到达它的总时间。因为每个点总是用到了它前面点的状态,且图没有重边,自环不用加边,就会想拓扑排序。

 

   对于各个点来说,从它的所有入边都能引出方案数和时间总数,时间总数在通过(u,v)路径转移时要乘上u的方案数。因为此时u已经可以转移了,说明u的拓扑序已经排到了,而v的拓扑序还没有排到,根据逻辑关系,我们要乘的是u的方案数,去转移v的方案数,有点像DP里面的刷表法。

 

总结:

   这几天老是被long long坑,对于这些要模的题或者其他答案较大的题,很有可能int相乘乘爆。例如

(long long)c=(int)a*(int)b

   当a*b超过int所能表示的整数范围时,它仍然返回int范围内的值,尽管左边是long long,但还是赋值为int。

(int)c=(int)a*(int)b%(int)质数

   在这种情况下因为*和%优先级相等,所以从左向右计算。当这个质数超过100000左右,或者说a,b本身较大,就会先计算a,b,也就可能乘爆。因此,我们要么在这个题地代码里尽可能多地定义long long,要么就在可能爆炸的地方打上括号(括号也很玄学,最好每两个运算符之间都打括号)。

 

Code:

#include<cstdio>
#include<cstring>
struct edge
{
    int n,v,nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[51000];
int head[10100],cnt=-1;
void add(int from,int to,int v)
{
    e[++cnt]=edge(to,v,head[from]);
    head[from]=cnt;
}
int s,t;
int q[123456],l=0,r=0;
int in[10100];
long long way[10100],tm[10100];//方案数和总用时
void bfs()
{
    in[s]=0;
    way[s]=1;
    q[++r]=s;
    while(l<r)
    {
        int k=q[++l];
        for(int i=head[k];~i;i=e[i].nxt)
        {
            way[e[i].n]+=way[k]%10000;
            tm[e[i].n]+=(tm[k]+way[k]*e[i].v%10000)%10000;记得加上tm[k]
            in[e[i].n]--;
            if(!in[e[i].n])
                q[++r]=e[i].n;
        }
    }
}
int main()
{
    int n,m,t0,u,v,w;
    scanf("%d%d%d%d%d",&n,&m,&s,&t,&t0);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        if(u==v)
            continue;
        add(u,v,w);
        in[v]++;
    }
    bfs();
    printf("%d\n",((way[t]-1)*t0+tm[t]+10000)%10000);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */