企业官网建设流程全解析

静态网站跟动态,wordpress百度推送插件,yellow片观看完整版,怎么样增加网站权重拓扑排序 1 有向⽆环图 若⼀个有向图中不存在回路#xff0c;则称为 有向⽆环图 (directed acycline graph)#xff0c;简称 DAG 图。 2. AOV ⽹ 举⼀个现实中的例⼦#xff1a;课程的学习是有优先次序的#xff0c;如果规划不当会严重影响学习效果。课程间的先 后次序…拓扑排序1有向⽆环图若⼀个有向图中不存在回路则称为有向⽆环图(directed acycline graph)简称 DAG 图。2.AOV ⽹举⼀个现实中的例⼦课程的学习是有优先次序的如果规划不当会严重影响学习效果。课程间的先 后次序可以⽤有向图表⽰在这种有向图中⽤顶点表⽰活动⽤有向边 Vi,Vj 表⽰活动Vi必须先于活动Vj进⾏这种有 向图叫做顶点表⽰活动的⽹络(Activity On Vertex Network)简称 AOV ⽹。AOV ⽹中不能有回路否则就不能确定回路中的活动究竟哪个先实施。因此⼀个可⾏的 AOV ⽹必须是 有向⽆环图。3拓扑排序拓扑排序的⽬标是将有向⽆环图中的所有结点排序使得排在前⾯的结点不能依赖于排在后⾯的结点。在课程问题中相当于就是找到⼀个排课的合法顺序。具体流程可借助队列进⾏1.将图中所有⼊度为 0 的点加⼊到队列中2.取出队头元素删除与该点相连的边。如果删除之后的后继结点的⼊度变为 0加⼊到队列中3.重复 2 操作直到图中没有点或者没有⼊度为 0 的点为⽌。拓扑排序判断是否有环跑⼀遍拓扑排序算法如果有结点没有进队那么就表明有环。4【模板】拓扑排序题⽬来源 洛⾕题⽬链接B3644 【模板】拓扑排序 / 家谱树难度系数 ★★题目描述有个人的家族很大辈分关系很混乱请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列使得每个人的后辈都比那个人后列出。输入格式第 1 行一个整数 N1≤N≤100表示家族的人数。接下来 N 行第 i 行描述第 i 个人的后代编号 ai,j​表示 ai,j​ 是 i 的后代。每行最后是 0 表示描述完毕。输出格式输出一个序列使得每个人的后辈都比那个人后列出。如果有多种不同的序列输出任意一种即可。输入输出样例输入 #1复制5 0 4 5 1 0 1 0 5 3 0 3 0输出 #1复制2 4 5 3 1【解法】模板题~【参考代码】#include iostream #include queue #include vector using namespace std; const int N 110; // 家族人数上限100设110留余量 int n; // 实际家族人数 vectorint edges[N]; // 邻接表edges[x]存x的所有后代x→后代的边 int in[N]; // in[y]y的入度y有多少个长辈 int main() { cin n; // 输入家族人数n // 第一步读入每个人的后代信息构建图统计入度 for(int i 1; i n; i) // 遍历第i个人 { int j; // 循环读入i的后代编号直到读到0结束 while(cin j, j) // 等价于cinj; while(j!0) { edges[i].push_back(j); // 记录i的后代j加边i→j in[j]; // j的入度1j多了一个长辈i } } // 第二步拓扑排序核心用队列实现 queueint q; // 队列存“入度为0的节点”没有长辈的人可优先输出 // 先把所有入度为0的节点加入队列 for(int i 1; i n; i) { if(in[i] 0) q.push(i); } // 第三步处理队列生成拓扑序 while(q.size()) // 队列不为空 { int x q.front(); // 取出队首节点当前无长辈的人 q.pop(); // 弹出队首 cout x ; // 输出该节点加入序列 // 遍历x的所有后代y相当于“删除x→y的边” for(auto y : edges[x]) { in[y]--; // y的入度-1少了一个长辈x的约束 if(in[y] 0) // y的入度为0→没有其他长辈了可输出 { q.push(y); } } } return 0; }5摄像头题⽬来源 洛⾕题⽬链接P2712 摄像头难度系数 ★★题目描述食品店里有 n 个摄像头这种摄像头很笨拙只能拍摄到固定位置。现有一群胆大妄为的松鼠想要抢劫食品店为了不让摄像头拍下他们犯罪的证据他们抢劫前的第一件事就是砸毁这些摄像头。为了便于砸毁摄像头松鼠歹徒们把所有摄像头和摄像头能监视到的地方统一编号一个摄像头能被砸毁的条件是该摄像头所在位置不被其他摄像头监视。现在你的任务是帮松鼠们计算是否可以砸掉所有摄像头如不能则输出还没砸掉的摄像头的数量。输入格式第 1 行一个整数 n表示摄像头的个数。第 2 到 n1 行是摄像头的信息包括摄像头的位置 x以及这个摄像头可以监视到的位置数 m之后 m 个数 y 是此摄像头可以监视到的位置砸了这些摄像头之后自然这些位置就监视不到了。输出格式若可以砸掉所有摄像头则输出“ YES”否则输出还没砸掉的摄像头的数量不带引号。输入输出样例输入 #1复制5 1 1 2 2 1 1 3 1 7 4 1 1 5 0输出 #1复制2说明/提示1≤n≤100。0≤m≤100。0≤x,y≤500。【解法】拓扑排序判断是否有环。直接跑⼀遍拓扑排序然后统计⼀下有多少摄像头没有出队。那么这些没有出队的摄像头就是环⾥⾯ 的元素。注意•有些位置可能没有摄像头需要判断⼀下。【参考代码】#include iostream #include queue #include vector using namespace std; const int N 510; // 位置编号上限是500设510留余量 int n; // 摄像头的个数 vectorint edges[N]; // 邻接表edges[x]存x能监视的所有位置x→y的边 int in[N]; // in[y]位置y的入度有多少个摄像头监视y bool st[N]; // st[x]true → 位置x有摄像头标记有效顶点 int main() { cin n; // 输入摄像头个数n // 第一步读入摄像头信息构建图标记有效顶点统计入度 for(int i 1; i n; i) // 遍历第i个摄像头 { int x, m, y; cin x m; // x摄像头位置m能监视的位置数 st[x] true; // 标记位置x有摄像头有效顶点 while(m--) // 读入m个被监视的位置y { cin y; edges[x].push_back(y); // 加边x→yx监视y in[y]; // y的入度1多一个摄像头监视y } } // 第二步拓扑排序初始化——入度为0的有效顶点加入队列 queueint q; for(int i 0; i 500; i) // 遍历所有可能的位置0~500 { // 条件位置i有摄像头st[i]true且入度为0in[i]0 if(st[i] in[i] 0) q.push(i); } // 第三步执行拓扑排序消除入度为0的顶点 while(q.size()) // 队列不为空 { auto x q.front(); // 取出队首位置x入度为0的有效顶点 q.pop(); // 弹出队首 // 遍历x能监视的所有位置y遍历边x→y for(auto y : edges[x]) { in[y]--; // y的入度-1x的摄像头被砸了不再监视y // 如果y是有效顶点有摄像头且入度变为0加入队列 if(st[y] in[y] 0) q.push(y); } } // 第四步统计环中的顶点数砸不掉的摄像头数 int ret 0; for(int i 0; i 500; i) { // 条件位置i有摄像头st[i]true且入度0还在环里 if(st[i] in[i]) ret; } // 输出结果没砸掉的数量为0则输出YES否则输出数量 if(ret 0) cout YES endl; else cout ret endl; return 0; }6最⼤⻝物链计数题⽬来源 洛⾕题⽬链接P4017 最⼤⻝物链计数难度系数 ★★★题目背景你知道食物链吗Delia 生物考试的时候数食物链条数的题目全都错了因为她总是重复数了几条或漏掉了几条。于是她来就来求助你然而你也不会啊写一个程序来帮帮她吧。题目描述给你一个食物网你要求出这个食物网中最大食物链的数量。这里的“最大食物链”指的是生物学意义上的食物链即最左端是不会捕食其他生物的生产者最右端是不会被其他生物捕食的消费者。Delia 非常急所以你只有 1 秒的时间。由于这个结果可能过大你只需要输出总数模上 80112002 的结果。输入格式第一行两个正整数 n、m表示生物种类 n 和吃与被吃的关系数 m。接下来 m 行每行两个正整数表示被吃的生物 A 和吃 A 的生物 B。输出格式一行一个整数为最大食物链数量模上 80112002 的结果。输入输出样例输入 #1复制5 7 1 2 1 3 2 3 3 5 2 5 4 5 3 4输出 #1复制5说明/提示各测试点满足以下约定测试点编号nm1,2≤40≤4003,4≤100≤2×1035,6≤103≤6×1047,8≤2×103≤2×1059,10≤5×103≤5×105对于 100% 的数据1≤n≤5×103,1≤m≤5×105【补充说明】数据中不会出现环满足生物学的要求。感谢 AKEE【解法】注意审题题⽬问的是⼀共有多少条路径拓扑排序的过程中进⾏动态规划。对于每⼀个节点 通过它的路径为前驱所有结点的路径总数之和。因此可以在拓扑排序的过程 中维护从起点开始到达每⼀个节点的路径总数。【参考代码】#include iostream #include vector #include queue using namespace std; // 常量N生物种类上限5010MOD取模值题目要求 const int N 5010, MOD 80112002; int n, m; // n生物种类数m吃与被吃的关系数 vectorint edges[N]; // 邻接表edges[x]存x被哪些生物吃x→yy吃x int in[N], out[N]; // in[y]y的入度有多少生物被y吃→y的食物数out[x]x的出度x被多少生物吃 int f[N]; // f[i]到生物i的食物链数量 int main() { cin n m; // 输入生物数n关系数m // 第一步读入吃与被吃关系构建图统计入度/出度 for(int i 1; i m; i) { int x, y; cin x y; // x被y吃 → 边x→y edges[x].push_back(y); // 加边x→yx的后继是y in[y]; // y的入度1y多了一个食物x out[x]; // x的出度1x多了一个捕食者y } // 第二步拓扑排序初始化——生产者入度为0加入队列f值1 queueint q; for(int i 1; i n; i) { if(in[i] 0) // 生产者没有生物被它吃它不吃任何生物 { f[i] 1; // 到生产者的路径数1只有自己 q.push(i); // 加入拓扑队列 } } // 第三步拓扑排序动态规划统计路径数 while(q.size()) // 队列不为空 { auto x q.front(); // 取出队首生物x当前无前置依赖的生物 q.pop(); // 弹出队首 // 遍历x的所有捕食者yx被y吃边x→y for(auto y : edges[x]) { // 到y的路径数 到x的路径数因为x→y是一条新路径取模避免溢出 f[y] (f[y] f[x]) % MOD; in[y]--; // y的入度-1x已经处理完y少了一个食物依赖 // 如果y的入度为0所有食物都处理完加入队列 if(in[y] 0) q.push(y); } } // 第四步统计所有顶级消费者出度为0的路径数之和 int ret 0; for(int i 1; i n; i) { if(out[i] 0) // 顶级消费者没有捕食者不被任何生物吃 { ret (ret f[i]) % MOD; // 累加路径数取模 } } // 输出结果 cout ret endl; return 0; }7杂物题⽬来源 洛⾕题⽬链接P1113 杂务难度系数 ★★★题目描述John 的农场在给奶牛挤奶前有很多杂务要完成每一项杂务都需要一定的时间来完成它。比如他们要将奶牛集合起来将他们赶进牛棚为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的因为这样才有更多时间挤出更多的牛奶。当然有些杂务必须在另一些杂务完成的情况下才能进行。比如只有将奶牛赶进牛棚才能开始为它清洗乳房还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作这个可以最早着手完成的工作标记为杂务 1。John 有需要完成的 n 个杂务的清单并且这份清单是有一定顺序的杂务 k (k1) 的准备工作只可能在杂务 1 至 k−1 中。写一个程序依次读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作并且你可以假定 John 的农场有足够多的工人来同时完成任意多项任务。输入格式第 1 行一个整数 n (3≤n≤10,000)必须完成的杂务的数目第 2 至 n1 行每行有一些用空格隔开的整数分别表示工作序号保证在输入文件中是从 1 到 n 有序递增的完成工作所需要的时间 len (1≤len≤100)一些必须完成的准备工作总数不超过 100 个由一个数字 0 结束。有些杂务没有需要准备的工作只描述一个单独的 0。保证整个输入文件中不会出现多余的空格。输出格式一个整数表示完成所有杂务所需的最短时间。输入输出样例输入 #1复制7 1 5 0 2 2 1 0 3 3 2 0 4 6 1 0 5 1 2 4 0 6 8 2 4 0 7 4 3 5 6 0输出 #1复制23【解法】拓扑排序的过程中进⾏动态规划。对于每⼀个事件 完成它的最⼩时间为完成前驱所有事件的最⼩时间中的最⼤值 当前事件的完 成时间。因此可以在拓扑排序的过程中维护每⼀个事件完成的最⼩时间然后更新当前事件的最 ⼩时间。【参考代码】#include iostream #include vector #include queue using namespace std; const int N 10010; // 杂务数量上限10000设10010留余量 int n; // 杂务总数 vectorint edges[N];// 邻接表edges[A]存“以A为准备工作的杂务B”边A→B int in[N]; // in[B]杂务B的准备工作数入度 int f[N]; // f[B]完成杂务B的最早开始时间等所有准备工作做完 int len[N]; // len[i]杂务i的完成耗时 int main() { cin n; // 输入杂务总数n // 第一步读入每个杂务的信息构建图统计入度存耗时 for(int i 1; i n; i) { int b, a; cin b len[b]; // b杂务序号len[b]该杂务的耗时 // 读入准备工作直到遇到0结束 while(cin a, a) // 逗号表达式先读a再判断a≠0 { edges[a].push_back(b); // 加边a→ba是b的准备工作 in[b]; // b的入度1多一个准备工作 } } // 第二步拓扑排序初始化——无准备工作的杂务入度为0加入队列 queueint q; for(int i 1; i n; i) { if(in[i] 0) // 没有准备工作可直接开始 q.push(i); } int ret 0; // 记录所有杂务的最大完成时间总最短时间 // 第三步拓扑排序动态规划计算完成时间 while(q.size()) // 队列不为空 { int a q.front(); // 取出队首杂务a所有准备工作已完成 q.pop(); // 弹出队首 // 计算杂务a的完成时间最早开始时间f[a] 耗时len[a] f[a] len[a]; // 更新总最短时间取当前最大的完成时间 ret max(ret, f[a]); // 遍历所有以a为准备工作的杂务b边a→b for(auto b : edges[a]) { // 杂务b的最早开始时间 自身当前值 和 a的完成时间的最大值等a做完才能开始b f[b] max(f[b], f[a]); in[b]--; // b的入度-1a的准备工作已完成 // 如果b的所有准备工作都完成入度为0加入队列 if(in[b] 0) q.push(b); } } // 输出总最短时间 cout ret endl; return 0; }