文档章节

sicily 1211 商人的宣传

Ciel
 Ciel
发布于 2013/01/17 18:28
字数 789
阅读 164
收藏 0

Description

 Bruce是K国的商人,他在A州成立了自己的公司,这次他的公司生产出了一批性能很好的产品,准备宣传活动开始后的第L天到达B州进行新品拍卖,期间Bruce打算将产品拿到各个州去做推销宣传,以增加其影响力。

K国有很多个州,每个州都与其他一些州相邻,但是K国对商人作宣传却有一些很奇怪的规定:
1、 商人只能从某些州到达另外一些州,即连通路线是单向的,而且有些州可能是到达不了的。
2、 商人不允许在同一个州连续宣传两天或以上,每天宣传完必须离开该州。
3、 商人可以多次来到同一个州进行宣传。

"我必须找出一条影响力最大的路线才行",Bruce想,"但我首先必须知道到底有多少这种符合规定的宣传路线可供我选择。"现在Bruce把任务交给了你。并且出于考虑以后的需要,你还要帮他算出给出的两州之间的路线的总数。

Input

输入文件第一行包含三个整数n,m,L(1≤n,L≤100),分别表示K国的州数、连通路线的数量,以及多少天后必须到达B州。接下来有m行,每行一队整数x,y(1≤x,y≤n),表示商人能从x州到达y州。
第m+2行为一个整数q(1≤q≤100),表示Bruce有q个询问。下面q行每行两个整数A,B(1≤A,B≤n),即A、B州的位置。

Output

输出文件包含q行,每行一个整数t,为所求的从A州到B州满足上述规定的路线总数。
输入数据中的询问将保证答案t在长整数范围内,即t<2 31

Sample Input

4 5 6
1 2
2 3
3 4
4 1
2 4
2
1 4
4 2

Sample Output

2
1

分析:

比较偷懒的做法是直接使用矩阵乘法。具体做法是,可以初始化地图矩阵m1所有节点为0,然后一旦联通则设为1,那么2天内由A到B的方法为M1*M1后得到的矩阵的第a行第b列,递推可以知道第l天方法数为矩阵吗m1连乘l-1次所得矩阵。这种方法写法简便,但是速度可能稍慢。

代码:

// Problem#: 1211
// Submission#: 1899573
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <cstring>
using namespace std;

#define MAX 100

int main() {
    int a, b;
    int m1[MAX][MAX] = {0};
    int m2[MAX][MAX] = {0};
    int m3[MAX][MAX] = {0};
    int n, m, l, q;
    cin >> n >> m >> l;
    while (m--) {
        cin >> a >> b;
        ++m1[a - 1][b - 1];
        ++m2[a - 1][b - 1];
    }
    for (int c = 0; c < l - 1; ++c) {
        memset(m3, 0, sizeof(m3));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j)
                for(int k = 0; k < n; ++k)
                    m3[i][j] += m1[i][k] * m2[k][j]; 
        }
        memcpy(m1, m3, sizeof(m1));
    }
    cin >> q;
    while (q--) {
        cin >> a >> b;
        cout << m3[a - 1][b - 1] << endl;
    }
    return 0;
}

© 著作权归作者所有

上一篇: sicily 1083 Networking
下一篇: sicily 1781 Knight
Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
IT人卖家乡特产,我真做了,我是信丰人,你们来捧场,好吗

做IT好多年了,一直有创业的想法,可这难易程度,对每个人而言都不尽相同。 自己规划了很久,可始终是在默默的编码做项目;常来这里看大家灌水,也是工作之余的一种快乐。 前段时间也有好些人...

xfbbd_com
2015/10/26
7.5K
76
WebLogic Server 12c (12.1.1)安装

下载地址: http://www.oracle.com/technetwork/middleware/weblogic/downloads/wls-main-097127.html 下载Installers with Oracle WebLogic Server and Oracle Coherence:的Generic (997 MB......

Mr_sheng
2017/11/29
0
0
不会用剑:那些伪互联网海盗们

我们很难弄清楚时光到底意味着什么,但每到年底,回首一年往事,有时会有很不真实的感觉。时光可以带给我们波澜壮阔、世事沧桑,繁华落尽、物是人非,经历过时光的洗涤,那些回忆总是像褪色的...

Chris Zhou
2017/08/22
0
0
LeetCode:Count and Say - 按照数字重复出现计数并生成字符串

1、题目名称 Count and Say(按照数字重复出现计数并生成字符串) 2、题目地址 https://leetcode.com/problems/count-and-say/ 3、题目内容 英文:The count-and-say sequence is the seque...

北风其凉
2015/08/07
209
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql-connector-java升级到8.0后保存时间到数据库出现了时差

在一个新项目中用到了新版的mysql jdbc 驱动 <dependency>     <groupId>mysql</groupId>     <artifactId>mysql-connector-java</artifactId>     <version>8.0.18</version> ......

ValSong
今天
5
0
Spring Boot 如何部署到 Linux 中的服务

打包完成后的 Spring Boot 程序如何部署到 Linux 上的服务? 你可以参考官方的有关部署 Spring Boot 为 Linux 服务的文档。 文档链接如下: https://docs.ossez.com/spring-boot-docs/docs/r...

honeymoose
今天
6
0
Spring Boot 2 实战:使用 Spring Boot Admin 监控你的应用

1. 前言 生产上对 Web 应用 的监控是十分必要的。我们可以近乎实时来对应用的健康、性能等其他指标进行监控来及时应对一些突发情况。避免一些故障的发生。对于 Spring Boot 应用来说我们可以...

码农小胖哥
今天
9
0
ZetCode 教程翻译计划正式启动 | ApacheCN

原文:ZetCode 协议:CC BY-NC-SA 4.0 欢迎任何人参与和完善:一个人可以走的很快,但是一群人却可以走的更远。 ApacheCN 学习资源 贡献指南 本项目需要校对,欢迎大家提交 Pull Request。 ...

ApacheCN_飞龙
今天
5
0
CSS定位

CSS定位 relative相对定位 absolute绝对定位 fixed和sticky及zIndex relative相对定位 position特性:css position属性用于指定一个元素在文档中的定位方式。top、right、bottom、left属性则...

studywin
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部