noip图论相关内容。
1． 图的存储。
相邻矩阵。a[i,j]表示结点i到结点j的距离。
边集数组。i,j,k 表示结点i与结点j相连接，权值为k
邻接表。方法一浪费空间。
tot[i]表示第i个结点连接边的数量。
a[i,j]表示第i个结点第j个连接的结点的结点序号。
方法二模拟链表节省空间。
last[点]=边记录和这个点相连的最后一条边。
pre[边]=边记录和同一点相连的上一条边。
other[边]=点记录的这条边的另一个点。
建图。readln(x,y);
inc(e);
pre[e]:=last[x];
last[x]:=e;
other[e]:=y;
2． 图的遍历。
dfsprocedure dfs(x:longint);
beginbool[x]:=true;
for i:=1 to n do
if i未被访问 and 与i连接 then dfs(i);
end;begin
for i:=1 to n do
if bool[i]=false then dfs(i);
end;bfs
procedure (x:longint);
var i,l,r,j:longint;
beginl:=0;r:=1;
bool[x]:=true;
q[r]:=x;
while l>r do
begininc(l);
i:=q[l];
for j:=1 to n do
if (a[i,j]=1) and (bool[j]=false) then
begin inc(r);q[r]:=j;bool[j]:=true; end;
end;end;
3．传递闭包。
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
f[i,j]=f[i,j] or (f[i,k] and f[k,j]);
4. 最短路径。
floyed o(n^3)
多源最短路径（多源最长路径）
当计算最短路径时，要求图中不能有负权回路。
当计算最长路径时，要求图中不能有正权回路。
f[i,j]表示i到j的最短路径。
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
最短路径 f[i,j]=min(f[i,j],f[i,k]+f[k,j]);最长路径 f[i,j]=max(f[i,j],f[i,k]+f[k,j]);
dijkstra o(n^2)
单源最短路径。
运用松弛技术，逐步更新两结点的距离，图中不能有负权。
fillchar(bool,sizeof(bool),false);
f[1]=0 f[i]=+oo (1for i:=1 to n do
beginmin:=+oo;
for j:=1 to n do
if (not(bool[j]))and (f[j]begin min:=f[j];q:=j; end;
bool[q]:=true;
for j:=1 to n do
if (not(bool[j]))and (f[j] end;
writeln(f[x]);
end.bellman-ford o(nm)
单源最最路径。
运用松弛计数，可以计算负权，逐步更新两点的距离。
for i:=1 to m do
readln(e[i].a,e[i].r,e[i].w); 边集数组输入。
f[1]:=0; f[i]:=oo; (1for i:=1 to n-1 do
beginchange:=false;
for j:=1 to m do
beginif f[e[j].a]+e[j].w f[e[j].b]:=f[e[j].a]+e[j].w;
change:=true;
end;if not(change) then break;
end;writeln(f[k]);
end.spfa
单源最短路。
bellman-ford 的队列实现方式，spfa采用邻接表的数据结构。
tot[i]表示第i个结点相邻的结点数。
f[i]表示结点1到i的最短距离。
map[i,j]表示i结点第j个结点的序号。
que[i]当前队列。
f[0]:=0;
f[i]:=oo;
l:=0;r:=1;
que[r]:=1;
while l begin
inc(l);
q:=que[l];
for i:=1 to tot[q] do
if a[q,map[q,i]]+f[q] begin
inc(r);
f[map[q,i]]:a[q,map[q,i]]+f[q];
que[r]:=map[q,i];
end;end;
writeln(f[x]);
end;5. 最小生成树(mst)
kruskal o(eloge) 适合于边稀疏。
贪心+快速排序+并查集。
kuai(1,tot) 升序排列。
for i:=1 to tot do
beginx:=find(e[i].l); y:=find(e[i].r);
if x<>y then
beginsum:=sum+e[i].w;
s[x]:=y;
inc(t);
if t=n-1 then break;
end;end;
prim o(n^2) 适合于点密集。
cost[i]表示结点i到集合的距离。
index[i]表示第i个点连接的点。
每次扩展距离集合最短的结点。
for i:=1 to n do
begincost[i]:=a[1,i];
index[i]:=1;
end;for i:=1 to n-1 do
beginmin:=+oo;
for j:=1 to n do
if (cost[j]0) then
beginmin:=cost[j];
k:=j;end;
cost[k]:=0;
for j:=1 to n do
if a[k,j]begin
cost[j]:=a[k,j];
index[j]:=k;
end;end;
for i:=2 to n do
max:=max+a[i,index[i]];
writeln(max);
end.6. 并查集。
①返回集合跟结点。
function find(x:longint):longint;
beginif x=s[x] then exit(s[x]) else
begins[x]:=fins(s[x]);
exit(s[x]);
end;end;
合并。procedure bing(a,b:longint);
var v1,v2:longint;
beginv1:=find(a); v2:=find(b);
if v1<>v2 then s[v1]:=v2;
end;查询集合个数（hash）
for i:=1 to n do
if bool[find(i)]=false then begin bool[find(i)]:true;inc(tot); end;
7. 二分图匹配。
function dfs(a:longint):longint;
var i:longint;
beginfor i:=1 to n do
if bool[i]=false then
beginbool[i]:=true;
if (seat[i]=0) and (dfs(seat[i])=1) then
beginseat[i]=a;
exit(1);
end;end;
exit(0);
end.for i:=1 to n do
beginfillchar(bool,sizeof(bool),false);
dfs(i);
end;noip树相关内容。
1． 树的遍历
procedure bian(x:longint);
var i:longint;
beginfor i:=1 to n do
if 未被访问 and i是x的儿子 then bian(i);
访问处理(i);
end;2. 二叉树树的存储。
一般存储方法。
const m=树的结点数。
typenode=record
data:datatype
l,r,f:0..m; 左儿子，右儿子，父亲结点。
end;treetype=array[1..m] of node;
var tree:treetype
特殊存储完全二叉树父节点i 左儿子2*i 右儿子 2*i+1
由于以上二叉树性质，完全二叉树可以由线性数组存储（堆）
3.二叉树的遍历。
前序遍历。procedure preorder(i:longint);
beginif bool[i]=true then
begin访问处理 a[i].data
preorder(a[i].l);
preorder(a[i].r);
end;end;
中序遍历。procedure inorder(i:longint);
beginif bool[i]=true then
begininorder(a[i].l);
访问处理 a[i].data
inorder(a[i].r);
end;end;
后序遍历。procedure postorder(i:longint);
beginif bool[i]=true then
begin
postorder(a[i].l);
postorder(a[i].r);
访问处理a[i].data
end;
Noip2019模拟赛
牙林一中oi队noip2011模拟赛 四 注意事项 请自行完成题目，切勿讨论。题1 阿猫的实验。问题描述 阿猫很喜欢生物学。他还在今年的全国中学生生物学联赛中获得了一等奖。一天，阿猫在实验室听说了这样一种繁殖能力很强的老鼠。这种老鼠在出生后的第一个月，可以生出a 对老鼠 第二个月，可以生出b 对老鼠...
NOIP2019初赛模拟试题
一 选择一个正确答案 a b c d 填入每题的括号内 每题1.5分，共30分 1.下面四个不同进制的数，最小的一个数是 a 11011001 2 b 75 10 c 37 8 d a7 16 2 计算机的软件系统通常分为 a.系统软件与应用软件b.高级软件与一般软件 c.军用软件与民用软件d.管理...
NOIP2019初赛试题模拟
一 选择题 皆为单选 1 以下谁是二进制思想的最早提出者？a.伏羲 b.姬昌 c.莱布尼茨 d.柏拉图。2 以下哪个概念和公孙龙的 指物论 中的 指 字含义相近？a.变量 b.数组 c.对象 d.指针。3 蔺相如，司马相如 魏无忌，长孙无忌。下列哪一组对应关系与此类似？4 秦始皇吞并六国采用了以下哪...