1076 Forwards on Weibo
1. 这题说的是，微博上人们之间有关注和被关注的关系，如果一个人发博，他的追随者就可能转发，追随者的追随者又可能转发，以此类推。现在给定一个人，求其微博可能被转发的人数，但是注意有一个关注链长的上限，超过这个上限认为不会再转发。可见要有层数这个属性。
2. 本题在BFS专题下，但是不需要两个BFS函数，因为不用考虑图是不是强连通图，对于每一个人，关注他所在的强连通子图就好了，所以只需要一个BFS函数。
3. 由于BFS不像DFS有嵌套，所以很多变量是局部还是全局，判断顺序的先后要求都没那么高了，因为不会有覆盖问题。
4. 注意读清楚题目，我设置的邻接矩阵G[i][j]表示i的粉丝是j，但是读入的时候给出的是每个人的追随对象。不要弄反了。
这是例题的图示
AC代码
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
typedef long long LL;using namespace std;const int maxn = 1010;//总人数上限 int totalNum,maxL;bool G[maxn][maxn] = {0};int BFS(int idx){int layer[maxn] = {0};//层数int forwards = 0;//可能的转发数bool inq[maxn] = {0};//已经入队的下标 queue<int> Q;Q.push(idx);inq[idx] = 1;while(!Q.empty()){int now = Q.front();Q.pop();for(int k=1;k<=totalNum;k++){if(G[now][k]==1&&inq[k]==0){layer[k] = layer[now]+1;if(layer[k]<=maxL){Q.push(k);inq[k]=1;forwards++;}else break; } }}return forwards;} int main(){scanf("%d %d",&totalNum,&maxL);for(int i=1;i<=totalNum;i++){int num;scanf("%d",&num);for(int k=0;k<num;k++){int j;scanf("%d",&j);G[j][i] = 1;// i追随很多j }}int qNum;scanf("%d",&qNum);while(qNum--){int idx;scanf("%d",&idx); printf("%d\n",BFS(idx));}return 0;
}相关文章：
2014年个人工作总结
2014年的日常工作，从技术支持岗位调到市场.社区岗位上：日常技术处理工作变为博客、微信、微博、市场活动策划、发送奖品等。如果以此为界：即毕业10年内的主要是软件研发、团队管理、项目管理；第二个十年开始，有幸从事市…
DAL(数据库访问层)
using System;using System.Collections.Generic;using System.Linq;using System.Web;using System.Data;using System.Data.SqlClient;using System.Configuration; /// <summary>///DBHelper 的摘要说明/// </summary>public static class DBHelper{ public …
Navicat for Oracle
1、先解压Navicat for Oracle到任意目录 2、将instantclient-basic-nt-12.1.0.2.0解压到1中目录的instantclient_10_2文件夹下（推荐，可随意） 3、将instantclient-sqlplus-nt-12.1.0.2.0解压到instantclient_10_2文件夹中的 instantclient_12_…
1013 Battle Over Cities(图的DFS解法)
这题的背景是战争年代，假如城市1被占领，那么所有和城市1相关的公路都要被炸毁，但是这样一来，2和3就不连通了，所以需要补修一条23之间的公路。但是换做城市2或3被占领，1和另一座城市是联通的，并不…
你必须了解的微服务架构设计的10个要点！
近来，几乎人人都在谈论微服务。微服务之所以火热也是因为相对之前的应用开发方式有很多优点，如更灵活、更能适应现在需求快速变更的大环境等。本文将介绍微服务架构设计中的一些要点。 微服务架构设计时有哪些要点呢？先看下图是 Spring Cloud…
企业信息化中常见决策点应对
我和一位朋友在聊天的时候，谈起在甲方的做信息化，和在乙方做信息化的不同点在于，在甲方做信息化，需要搞定为什么要上一个项目。而乙方参与进来的时候，项目其实已经启动了。 是的，作为甲方的我们，…
WebView调试
https://developer.chrome.com/devtools/docs/remote-debugging 转载于:https://www.cnblogs.com/daishuguang/p/4194882.html
1013 Battle Over Cities(并查集解法)
关于背景的介绍见1013 Battle Over Cities(图的DFS解法) DFS就是不算特定结点后数连通子图的总数，再减一。我想着那么并查集就是数不算特定节点后，集合元素(根)的个数。但是我弄错了一件事，我是边输入，边合并，然后对于…
FastDFS为什么要结合Nginx？
为什么选择Nginx Nginx 是一个很牛的高性能Web和反向代理服务器, 它具有有很多非常优越的特性: 在高连接并发的情况下，Nginx是Apache服务器不错的替代品: Nginx在美国是做虚拟主机生意的老板们经常选择的软件平台之一. 能够支持高达 50,000 个并发连接数的响应, 感谢…
STL容器[34]
SERVER以读打开FIFO；CLIENT以写打开FIFO；SERVER关闭FIFO；CLIENT向当前FIFO写数据，此时CLIENT获得一个SIGPIPE信号。如果忽略该信号，那么write将返回-1，ERRNO为EPIPE向一个写打开，当对端已经关闭…
企业可视化报表工具选型经验分享
选型背景 我们是一家面向金融行业的系统集成商，每年要做十几个项目（看得出来我们并不大/笑哭），项目分大小、做事分先后，可不管怎样都绕不开数据，数据处理经常占项目的大头，所以经常会选择一些市…
1003 Emergency(Dijkstra，Bellman-Ford，SPFA三种解法)
目录 1. Dijkstra解法 2. Bellman-Ford解法 3. SPFA解法 4. Dijkstra解法AC代码 5. Bellman-Ford解法AC代码 6. SPFA解法AC代码 1. Dijkstra解法 这题不仅涉及到基础的解法，还涉及到第二标准(累计军队数量)，以及还要记录最短路径条数。这些都是在…
存储过程4-前台
代码 ALTERproc[dbo].[P_CheckCode](retintoutput,nIdint,tagnvarchar(50),cCodenvarchar(50),nHotelIdint)asbeginifUpper(tag)B_AREAbeginifexists(select1fromB_Area wherecCodecCodeandnHotelIdnHotelIdandnId<>nId) setret1elsesetret-1endelseifUpper(t…
安卓学习-其他-文件读写
在android中的文件放在不同位置，它们的读取方式也有一些不同。 本文对android中对资源文件的读取、数据区文件的读取、SD卡文件的读取及RandomAccessFile的方式和方法进行了整理。供参考。 一、资源文件的读取： 1) 从resource的raw中读取文件数据&#x…
X5同层播放器应用实践
移动端浏览器中的video元素是比较特别的，早期无论是在iOS还是Android的浏览器中，它都位于页面的最顶层，无法被遮挡。后来，这个问题在iOS下得到了解决。但是对Android的大部分浏览器来说，问题仍然存在。X5是腾讯基于Web…
1007 Maximum Subsequence Sum(两种思路)
1.解法1 思路 对于动态规划来说，最关键的就是找到状态转移方程，本题设置一个前向数组，元素predp[i]表示的是以元素i结尾的连续数列和的最大值，转移方程是predp[i] max(predp[i-1]a[i],a[i])。要做的事就是完成这个dp数组&#x…
C#学习-EF在三层中使用
1.搭建普通三层 DAL层，BLL层，Model层，Web层； DAL层引用Model层 BLL层引用DAL层和Model层 Web层引用BLL层和Model层 2.实现EF三层的搭建（添加引用，修改配置信息） 2.1添加EF对象 在Model中添加一个…
各大IT公司笔试真题汇总开发人员一定要加入收藏夹的网站(收藏)
巨人网络java笔试基础题分享 http://www.coderarea.net/bbs/read.php?tid834 百度笔试题 http://www.coderarea.net/bbs/read.php?tid811 百度2010校招运维部门笔试 http://www.coderarea.net/bbs/read.php?tid779 百度2010年校园招聘软件测试笔试题 http://www.coderarea.n…
Python编写Hive UDF
2019独角兽企业重金招聘Python工程师标准>>> 1. 目的 从string类型的字段中解析并汇总每种category类型的总amount 2. 素材 表名：test_table order_no hotel_seq discount_detail D8662EF4E 10212527 NULL 45C024849 …
1045 Favorite Color Stripe(LIS解法)
解题思路 本题属于Longest Increasing Sequence最长不下降子序列，但是要注意，LIS当中不会有无效的元素，而本题是有的，所以先要把无效元素过滤掉，才能转化成为LIS问题。 这里用到了hashTable(用map更慢)，初…
5.8fork父子进程
实验4-2：fork父子进程 实验目的： 理解fork创建子进程的本质 实验要求： 1、按如下要求编写程序: （1）、打开一个有内容的文件; （2）、调用fork创建子进程; （3）、读文件…
word表格自动编号
选中全部内容--右键--项目符号和编号--自定义--编号样式--选01,02样式.则生成所有编号选中第二批编号,--重新编号,就又从01开始了转载于:https://www.cnblogs.com/wzshhynk/archive/2009/12/30/1635805.html
Vue API(directives) 自定义指令
前言：除了vue的内置指令以外，我们可以定义自定义指令。内置指令表相见：https://www.cnblogs.com/ilovexiaoming/p/6840383.html 我们定义一个最简单的 <script> export default {name: App,data(){return{yanse:red}},// 所有自定义指令…
1045 Favorite Color Stripe(LCS解法) 需再理解
解题思路 使用LCS方法解这一题，首先要把现有的颜色和Eva的颜色看成即将取材的序列s和e。 而且注意2个序列都要从1开始读入，因为递归边界（待后叙）。 dp[i][j]代表的是e[1]-e[i]和s[1]-s[j]的范围内，公共子序列的长度…
C++ primer第五版随笔--2015年1月6日
记录自己看这本书时的一些内容。 一、引用（reference） 引用为对象起了另外一个名字。例如： int ival1024； int &relVal1ival;//对，注意尽量不要用这方式：int& relvalival； int &rel…
Python性能分析指南——中
程序使用了多少内存？现在我们对计时有了较好的理解，那么让我们继续弄清楚程序使用了多少内存。我们很幸运，Fabian Pedregosa模仿Robert Kern的line_profiler实现了一个不错的内存分析器。首先使用pip安装:这里建议安装psutil包，因…
1040 Longest Symmetric String 需再做
解题思路 本题属于最长回文子串专题下。与之前的LIS和LCS的动规有两个较大的不同 1. 虽然最后也是要求长度，但是长度信息不再蕴含在dp数组当中，dp[i][j]表示的仅仅是从s[i]起s[j]止这一段是否是回文，所以为了提醒自己，我设置成了…
回顾2009，展望2010。
回顾2009，展望2010。 2009即将过去，总结2009年，计划2010年。 2009年12月31日。转载于:https://www.cnblogs.com/finehappy/archive/2009/12/31/1654975.html
Linux Mint 19 安装Gnome Boxes 新建失败
之前在Ubuntu论坛提出，一直没有解决.http://forum.ubuntu.org.cn/viewtopic.php?f65&t488821 后参照： https://askubuntu.com/questions/836703/ ... sue/836715对方报错： (gnome-boxes:15984): Boxes-WARNING **: wizard.vala:463: Fai…
1057 Stack
目录 解题思路 AC代码 解题思路 虽然题目的名字是栈，但是这题和栈的关系很小，甚至我都没有用到stack这个数据结构，而是用vector<int>的pop_back()来模拟栈的弹出。 主要考察的是：在线查询，也就是查询过程中…