科技公司网站模板下载有哪些做ppt的网站

科技公司网站模板下载,有哪些做ppt的网站,wordpress登录小工具,在线酒店预定网站制作简介 本篇介绍两道有关拓扑排序的问题#xff0c;难度为洛谷黄题 前置知识 拓扑排序就是一系列有不同优先级的事件的排列#xff0c;其中优先级相同的事情可以相互交换 关键结论一个图能进行拓扑排序的充要条件是它是一个有向无环图(DAG) 入度和出度的概念 1.入度#xf…简介本篇介绍两道有关拓扑排序的问题难度为洛谷黄题前置知识拓扑排序就是一系列有不同优先级的事件的排列其中优先级相同的事情可以相互交换关键结论一个图能进行拓扑排序的充要条件是它是一个有向无环图(DAG)入度和出度的概念1.入度以v为终点的边的数量称为v的入度2.出度以v为起点的边的数量称为v的出度入度出度与优先级的关系假如一个点的入度为0说明它的优先级最高假如一个点的出度等于0说明它的优先级最低第一篇题解模板题题目描述B3644拓扑排序B3644 【模板】拓扑排序 / 家谱树题目描述有个人的家族很大辈分关系很混乱请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列使得每个人的后辈都比那个人后列出。输入格式第1 11行一个整数N NN1 ≤ N ≤ 100 1 \le N \le 1001≤N≤100表示家族的人数。接下来N NN行第i ii行描述第i ii个人的后代编号a i , j a_{i,j}ai,j​表示a i , j a_{i,j}ai,j​是i ii的后代。每行最后是0 00表示描述完毕。输出格式输出一个序列使得每个人的后辈都比那个人后列出。如果有多种不同的序列输出任意一种即可。输入输出样例 #1输入 #15 0 4 5 1 0 1 0 5 3 0 3 0输出 #12 4 5 3 1思路分析模板题目就简单讲一下代码实现思路先统计每一个点的入度统计完所有点后将入度为0的点放入队列当中接着从这几个点向外延申把延申到的点的入度减1因为对于延申到的点来说前面的点已经被删除掉了如果入度减少到0放入队列当中即可。代码展示#includeiostream#includealgorithm#includequeue#includevectorusingnamespacestd;constintN110;vectorintans;vectorintnode[N];queueintq;intn;intin[N];voidbfs(){while(!q.empty()){inttq.front();q.pop();for(autox:node[t]){in[x]--;if(in[x]0){ans.push_back(x);q.push(x);}}}}intmain(){cinn;for(inti1;in;i){intx;while(cinxx){node[i].push_back(x);in[x];}}for(inti1;in;i)if(in[i]0){q.push(i);ans.push_back(i);}bfs();for(inti0;ians.size();i)coutans[i] ;return0;}细节分析注意一下这个题目的输出顺序前辈在前后辈在后入度为0的点(前辈)是先被放入ans当中的所以这道题顺序输出即可有些题目可能是倒序输出的后面讲的这中类型我们往往会采用栈这个结构存储答案因为最后直接弹出即可当然用vector存储也是可以的倒序输出即可。AI注释代码#includeiostream#includealgorithm#includequeue#includevectorusingnamespacestd;constintN110;// 节点数量的最大限制vectorintans;// 存储拓扑排序的结果vectorintnode[N];// 邻接表node[t] 存储节点t指向的所有邻接节点queueintq;// 拓扑排序用的队列存储入度为0的节点intn;// 总节点数intin[N];// 入度数组in[x] 表示节点x的入度有多少节点指向x// 拓扑排序核心Kahn算法基于入度队列voidbfs(){// 队列非空时持续处理入度为0的节点while(!q.empty()){inttq.front();// 取出队首的入度为0节点q.pop();// 遍历当前节点t的所有邻接节点xfor(autox:node[t]){in[x]--;// 销毁t后x的入度减1t不再指向x// 若x的入度变为0说明x无前置依赖可加入拓扑序列和队列if(in[x]0){ans.push_back(x);q.push(x);}}}}intmain(){cinn;// 输入节点总数// 输入每个节点的邻接关系构建有向图for(inti1;in;i){intx;// 循环输入节点i的邻接节点输入0时终止while(cinxx){node[i].push_back(x);// 构建边i → xin[x];// 节点x的入度1因为i指向x}}// 初始化队列将所有入度为0的节点加入队列无前置依赖可优先处理for(inti1;in;i)if(in[i]0){q.push(i);ans.push_back(i);// 入度为0的节点直接加入拓扑结果}// 执行拓扑排序的BFSbfs();// 输出拓扑排序结果for(inti0;ians.size();i)coutans[i] ;return0;}第二篇题解P2712摄像头题目描述P2712 摄像头题目描述食品店里有n nn个摄像头这种摄像头很笨拙只能拍摄到固定位置。现有一群胆大妄为的松鼠想要抢劫食品店为了不让摄像头拍下他们犯罪的证据他们抢劫前的第一件事就是砸毁这些摄像头。为了便于砸毁摄像头松鼠歹徒们把所有摄像头和摄像头能监视到的地方统一编号一个摄像头能被砸毁的条件是该摄像头所在位置不被其他摄像头监视。现在你的任务是帮松鼠们计算是否可以砸掉所有摄像头如不能则输出还没砸掉的摄像头的数量。输入格式第1 11行一个整数n nn表示摄像头的个数。第2 22到n 1 n1n1行是摄像头的信息包括摄像头的位置x xx以及这个摄像头可以监视到的位置数m mm之后m mm个数y yy是此摄像头可以监视到的位置砸了这些摄像头之后自然这些位置就监视不到了。输出格式若可以砸掉所有摄像头则输出“YES \texttt{YES}YES”否则输出还没砸掉的摄像头的数量不带引号。输入输出样例 #1输入 #15 1 1 2 2 1 1 3 1 7 4 1 1 5 0输出 #12说明/提示1 ≤ n ≤ 100 1 \leq n \leq 1001≤n≤100。0 ≤ m ≤ 100 0 \leq m \leq 1000≤m≤100。0 ≤ x , y ≤ 500 0 \leq x,y \leq 5000≤x,y≤500。思路分析这道题就是拓扑排序的问题当摄像头a能拍到摄像头b时你要拆掉b你首先得拆掉a这就是做事情的顺序题目要求我们在不被摄像头拍到的情况下能拆掉多少个摄像头也就是说我们根据这些摄像头的拓扑排序能拆掉几个摄像头其中的拓扑约束在题目中的表述是谁能监视到哪个位置如果a能监视到b说明a有一条指向b的边这道题为什么会问我们是否能拆掉所有摄像头呢此时我们就要回归一个图有拓扑排序的充要条件了从样例数据中我们可以发现这个图是存在环的有环这个图就没有完整的拓扑排序了只有部分我们要求的就是这个部分的拓扑序有几个元素然后做差即可。注意无论是自环还是和其他点一起构成的环都是无法排到拓扑序当中的自己可以模拟一下就知道了。几个坑点1.这个描述的不清不楚的输入我真服了以1 1 2为例子描述的是在1这个位置有一个摄像头它能看到一个位置这个位置是2。2.有些看到的位置它可能并没有摄像头比如3 1 7这个数据在位置3有一个摄像头有能看到一个位置这个位置是7但是整组数据里7这个位置并没有摄像头所以我们在读入的时候还要有一个st数组判该点有无摄像头代码展示#includeiostream#includealgorithm#includequeue#includevector#includecstringusingnamespacestd;constintN510;intn,cnt;vectorintbranch[N];queueintq;boolst[N];intin[N];voidbfs(){while(!q.empty()){autotq.front();q.pop();for(autox:branch[t]){in[x]--;if(st[x]in[x]0){coutx*endl;cnt;q.push(x);}}}}intmain(){cinn;for(inti1;in;i){intnum,m,x;cinnumm;st[num]true;for(inti1;im;i){cinx;branch[num].push_back(x);in[x];}}for(inti0;iN;i)if(st[i]in[i]0){cnt;q.push(i);}bfs();if(n-cnt0)coutYESendl;elsecoutn-cntendl;return0;}细节分析建议大家都用第一种写法第二种很危险AI注释代码#includeiostream#includealgorithm#includequeue#includevector#includecstringusingnamespacestd;constintN510;// 节点摄像头位置的最大编号限制intn,cnt;// n摄像头总数cnt成功销毁的摄像头数量vectorintbranch[N];// 邻接表branch[t]存储摄像头t监视的所有位置queueintq;// 拓扑排序队列存储可销毁的摄像头入度为0boolst[N];// st[i]true 表示i是摄像头的位置intin[N];// 入度数组in[x]表示位置x被多少个摄像头监视// 拓扑排序Kahn算法销毁可移除的摄像头更新依赖voidbfs(){// 队列非空时持续处理可销毁的摄像头while(!q.empty()){autotq.front();// 取出队首可销毁的摄像头位置q.pop();// 遍历当前摄像头t监视的所有位置xfor(autox:branch[t]){in[x]--;// 销毁t后x被监视的次数减1入度-1// 若x是摄像头位置 且 入度为0无其他摄像头监视则x可销毁if(st[x]in[x]0){coutx*endl;// 调试输出标记可销毁的摄像头xcnt;// 销毁数1q.push(x);// x入队后续处理其监视的位置}}}}intmain(){cinn;// 输入摄像头总数// 输入每个摄像头的信息位置num 监视位置数m 监视的位置列表for(inti1;in;i){intnum,m,x;cinnumm;// num摄像头位置m该摄像头监视的位置数量st[num]true;// 标记num是摄像头位置// 读取m个被监视的位置构建邻接表更新入度for(inti1;im;i){cinx;branch[num].push_back(x);// 摄像头num监视位置xin[x];// 位置x的入度1被num监视}}// 初始化队列找出所有「是摄像头入度为0」的位置初始可销毁for(inti0;iN;i)if(st[i]in[i]0){cnt;// 初始销毁数1q.push(i);// 入队等待处理}bfs();// 执行拓扑排序销毁所有可销毁的摄像头// 输出结果全部销毁则输出YES否则输出未销毁的数量if(n-cnt0)coutYESendl;elsecoutn-cntendl;return0;}一点延申我们如何输出字典序最小的拓扑序呢将队列改为优先队列即可因为本人比较懒所以注释都是ai加的#includeiostream#includevector#includequeueusingnamespacestd;constintN1e510;vectorintg[N];// 邻接表intind[N];// 入度数组intmain(){intn,m;cinnm;// 读入m条边while(m--){inta,b;cinab;g[a].push_back(b);ind[b];// b的入度1}// 最小堆优先队列保证字典序最小priority_queueint,vectorint,greaterintpq;// 入度为0的节点入队for(inti1;in;i){if(ind[i]0)pq.push(i);}vectorintans;// 存储拓扑序列while(!pq.empty()){intupq.top();pq.pop();ans.push_back(u);for(intv:g[u]){ind[v]--;// 删除边 u-vif(ind[v]0)// 入度为0则入队pq.push(v);}}// 输出结果if(ans.size()!n){cout图中存在环无法拓扑排序\n;}else{for(intx:ans)coutx ;coutendl;}return0;}