怎么发现网站漏洞而做软件网站收录查询代码
目录
一、路径
1.1解题思路
1.2程序设计
填空题
二、出差
2.1解题思路
2.2程序设计
三、图的应用——最小生成树
3.1Prim算法
3.2kruskal算法
两个关键技术
一、路径
单元最短路：SPFA/Floyd/Dijiksla
图论问题：建图 套模版
1.1解题思路
|a-b|>21 两个节点之间没有边相连；
|a-b|<=21 两个节点之间有一条长度为a和b的最小公倍数的无向边相连。
1.2程序设计
填空题
import os
import sys# 请在此输入您的代码
import math
def lcm(a,b):return int(a*b/math.gcd(a,b))n = 2021
g = [[0 for i in range(1,n+2)]for j in range(1,n+2)]
for i in range(1,n+1):for j in range(1,n+1):if i == j:g[i][j] = g[j][i]=0elif abs(i-j)<=21:g[i][j] = g[j][i]=lcm(i,j)else:g[i][j]=10000000
for k in range(1,n+1):for i in range(1,n+1):for j in range(1,n+1):if g[i][j]>g[i][k]+g[k][j]:g[i][j]=g[i][k]+g[k][j]
print(g[1][n]) 二、出差
2.1解题思路
2.2程序设计
import os
import sys
from heapq import *class Des:def __init__(self,tar,dis):self.tar = tarself.dis = disdef __lt__(self,other):return self.dis < other.dis
INF = 1<<64
n,m = map(int,input().split())
edges = [[] for _ in range(n+1)]
vis = [False for _ in range(n+1)]
dis = [INF for _ in range(n+1)]
time = [0]; time.extend(list(map(int,input().split())))
time[n] = 0
dis[1] = 0
que = [Des(1,dis[1])]
for _ in range(m):a,b,c = map(int,input().split())edges[a].append((b,c))edges[b].append((a,c))while que:now = heappop(que)if vis[now.tar]: continuevis[now.tar] = Truefor node,val in edges[now.tar]:if dis[node] > dis[now.tar] + time[node] + val:dis[node] = dis[now.tar] + time[node] + valheappush(que,Des(node,dis[node]))print(dis[n])三、图的应用——最小生成树
图的应用主要包括：最小生成（代价）树、最短路径、拓扑排序和关键路径。我们需要掌握学会手工模拟给定图的各个算法的执行过程。此外，还需掌握对给定模型建立相应的图去解决问题的方法。
在无向图中，连通而且不含有圈（环路）的图，成为树。一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。
若无向连通图G的边数比顶点数少1，即G本身是一棵树时，则G的最小生成树就是它本身。最小生成树的边数为顶点数减1。
最小生成树MST：一个有n个结点的连通图的生成树是原图的极小连通子图，包含图中的所有n个结点，并且边的权值之和最小。
3.1Prim算法
对点进行贪心操作：“最近的邻居一定在MST上”。 从任意一个点u开始，把距离它最近的点v加入到MST中；下一步，把距离{u, v}最近的点w加入到MST中；继续这个过程，直到所有点都在MST中。
3.2kruskal算法
对边进行贪心操作：“最短的边一定在MST上”。 从最短的边开始，把它加入到MST中；在剩下的边中找最短的边，加入到MST中；继续这个过程，直到所有点都在MST中。
两个关键技术
（1）对边进行排序。
（2）判断圈，即处理连通性问题。这个问题用并查集简单而高效，并查集是kruskal算法的绝配。
求第一个图的最小生成树：
使用并查集；
写出四个顶点/祖先都是自己：1 2 3 4 5
node方式存储边 对边从小到大排序
node{from, to,weight}
权值 连边
3 1,2
4 3,4
5 2,5
6 1,5
7 2,4
9 3,5
10 4,5
贪心算法：选择最小权值开始
判断是否在同一集合内
Find(1)find(2)；
故使用merge(1,2)进行“合并”连边操作
在图上体现的是1 2顶点连边
处理第二条边
3 4不在同一个集合内，merge(3,4)
处理第三条边
2 5不在同一个集合内，merge(2,5)
处理第四条边
Find(1)=find(5)
1 5已经连边（通过顶点2）
故不可以使用merge
但可以使用merge(2,4)
已经都在同一个集合内，到此结束
import mathclass Edge:x = 0y = 0w = 0.0def __init__(self, x, y, w):self.x = xself.y = yself.w = wdef find(x):if f[x]==x:return f[x]else:f[x] = find(f[x])return f[x]def merge(x,y):xx = find(x)yy = find(y)if xx!=yy:f[yy] = xxif __name__ == '__main__':m = int(input())a = list(map(int, input().split()))n = int(input())x = [0 for i in range(n + 2)]y = [0 for i in range(n + 2)]for i in range(n):b = list(map(int, input().split()))x[i + 1] = b[0]y[i + 1] = b[1]edge_list = []maxvalue = 0num = 0for i in range(1, n + 1):for j in range(i + 1, n + 1):w = math.sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]))edge = Edge(i, j, w)edge_list.append(edge)edge_list.sort(key=lambda x: x.w)f = [i for i in range(n + 1)]for i in edge_list:if find(i.x)!=find(i.y):merge(i.x,i.y)maxvalue = max(maxvalue,i.w)num+=1if num==n-1:breakans = 0for i in range(m):if a[i]>=maxvalue:ans+=1print(ans)
（2023年3月28日 11:25首次发布）