企业官网建设流程全解析

dede程序网站如何查看百度蜘蛛,司局网站维护廉政风险建设,中国三北防护林体系建设网站,wordpress配置ssl题目描述 本题要求计算在一个由单向街道组成的城市中#xff0c;从每个交叉路口到另一个交叉路口的不同路径数量。交叉路口用非负整数标识#xff0c;单向街道由一对整数 jjj kkk 表示#xff0c;代表从 jjj 到 kkk 的单向街道。若两个交叉路口之间存在无穷多条路径#x…题目描述本题要求计算在一个由单向街道组成的城市中从每个交叉路口到另一个交叉路口的不同路径数量。交叉路口用非负整数标识单向街道由一对整数j jjk kk表示代表从j jj到k kk的单向街道。若两个交叉路口之间存在无穷多条路径即存在环路则输出− 1 -1−1。输入包含多个城市的数据每个城市以街道数量开始随后是若干对整数表示街道。每个城市的交叉路口编号从0 00到最大编号。要求输出一个矩阵其中M [ j ] [ k ] M[j][k]M[j][k]表示从j jj到k kk的路径数若无穷多则输出− 1 -1−1。题目分析本题本质上是求有向图中任意两点间的路径数量并处理存在环路导致路径数无穷的情况。由于交叉路口数量不超过30 3030可以使用Floyd-Warshall \texttt{Floyd-Warshall}Floyd-Warshall算法的变种来解决。关键点在于初始化矩阵m a t r i x [ i ] [ j ] 1 matrix[i][j] 1matrix[i][j]1若存在从i ii到j jj的直接边。使用Floyd-Warshall \texttt{Floyd-Warshall}Floyd-Warshall算法累积路径数m a t r i x [ i ] [ j ] m a t r i x [ i ] [ k ] × m a t r i x [ k ] [ j ] matrix[i][j] matrix[i][k] \times matrix[k][j]matrix[i][j]matrix[i][k]×matrix[k][j]。若存在环路即m a t r i x [ k ] [ k ] 0 matrix[k][k] 0matrix[k][k]0则所有经过k kk的路径数都会变成无穷大即设置为− 1 -1−1。解题思路读入数据对于每个城市读入街道数量然后读入每一条街道更新邻接矩阵并记录最大的交叉路口编号。Floyd-Warshall \texttt{Floyd-Warshall}Floyd-Warshall算法计算路径数第一遍三重循环对于每个中间节点k kk更新m a t r i x [ i ] [ j ] m a t r i x [ i ] [ k ] × m a t r i x [ k ] [ j ] matrix[i][j] matrix[i][k] \times matrix[k][j]matrix[i][j]matrix[i][k]×matrix[k][j]。这利用了动态规划的思想计算从i ii到j jj经过k kk的路径数。第二遍三重循环检查每个节点k kk是否在环上m a t r i x [ k ] [ k ] 0 matrix[k][k] 0matrix[k][k]0。如果是则对于所有i ii和j jj若m a t r i x [ i ] [ k ] matrix[i][k]matrix[i][k]和m a t r i x [ k ] [ j ] matrix[k][j]matrix[k][j]都非零说明从i ii到j jj的路径可以经过该环无限次因此m a t r i x [ i ] [ j ] − 1 matrix[i][j] -1matrix[i][j]−1。输出结果按照格式输出矩阵。时间复杂度Floyd-Warshall \texttt{Floyd-Warshall}Floyd-Warshall算法的时间复杂度为O ( n 3 ) O(n^3)O(n3)其中n ≤ 30 n \leq 30n≤30因此完全可以在规定时间内完成。代码实现// Numbering Paths// UVa ID: 125// Verdict: Accepted// Submission Date: 2015-11-27// UVa Run Time: 0.000s//// 版权所有C2015邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;#defineMAXV31intmatrix[MAXV][MAXV];intlargest;voidfloyd(){for(intk0;klargest;k)for(inti0;ilargest;i)for(intj0;jlargest;j)matrix[i][j]matrix[i][k]*matrix[k][j];for(intk0;klargest;k)if(matrix[k][k])for(inti0;ilargest;i)for(intj0;jlargest;j)if(matrix[i][k]matrix[k][j])matrix[i][j]-1;}intmain(intac,char*av[]){intintersections;intcases0;intstart,end;while(cinintersections){largest0;memset(matrix,0,sizeof(matrix));for(inti1;iintersections;i){cinstartend;matrix[start][end]1;largestmax(largest,max(start,end));}floyd();coutmatrix for city casesendl;for(inti0;ilargest;i){coutmatrix[i][0];for(intj1;jlargest;j)cout matrix[i][j];coutendl;}}return0;}总结本题通过Floyd-Warshall \texttt{Floyd-Warshall}Floyd-Warshall算法的变种巧妙地解决了有向图中路径计数的问题并处理了环路导致的无穷路径情况。代码简洁高效适合作为图论中路径计数问题的经典例题。