资源描述：
《信息学竞赛图论习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图论算法最小生成树算法(Prim算法)
单源最短路径算法(Dijkstra算法)
任意结点最短路径算法(Floyd算法)
求有向带权图的所有环
Bellman-Ford算法
计算图的连通性
计算最佳连通分支
计算拓扑序列
图论算法习题网络建设问题
最短变换问题
挖地雷
乌托邦城市
乌托邦交通中心
某大学准备在校园网中构建校园网络，已知在校园网中选好了N（N<1000）个点，并准备在这些点安装网络设备和电脑。若要将N个点互相连接起来，问怎样布线才能使得总距离最短，两点间的布线长度等于这两个点的几何距离。【输入】network.in输入文件的第一行为一个正整数N(1≤N≤100)。接下
2、来N行，每行2个数U,V，表示坐标。【输出】network.out输出最短路径距离（保留两位小数）【样例数据】 【输入】500010-110-10【输出】4.00{思路分析：此题可以应用PRIM算法解决，关键是根据输入文件算出图的邻接矩阵，然后可以直接应用PRIM算法。}programnetwork;constvmax=100;varw:array[1..vmax,1..vmax]ofreal;x,y:array[1..vmax]ofreal;i,j,k,v,e:integer;23sum:real;procedureprim(v0:integer);varflag:array[1
3、..vmax]ofboolean;min:real;prevk,nextk:integer;beginfillchar(flag,sizeof(flag),false);flag[v0]:=true;fori:=1tov-1dobeginmin:=1e38;fork:=1tovdoifflag[k]thenforj:=1tovdoif(notflag[j])and(w[k,j]0)thenbeginmin:=w[k,j];nextk:=j;prevk:=k;end;ifmin<>1e10thenbeginflag[nextk]:=true;{wri
4、teln(prevk,'',nextk,'',min:0:2);此部分输出每个结点对的距离，因题目不要求所以不输出。}sum:=sum+min;end;end;end;{prim}beginassign(input,'network.in');reset(input);assign(output,'network.out');rewrite(output);fillchar(w,sizeof(w),0);readln(v);fori:=1tovdoreadln(x[i],y[i]);fori:=1tovdo{计算图的邻接矩阵}beginforj:=i+1tovdobeginw[i,
5、j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));23w[j,i]:=w[i,j];end;end;sum:=0;prim(1);writeln(sum:0:2);close(input);close(output);end.无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。【Prim算法思想】任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。【最小生成树算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城
6、市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？【输入】第一行两个数v(v<=200),e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权w(w<1000)。【输出】v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。 【输入样例】6101210151916212352462611346451846145633 【输出样例】121023524626114518 原 图最小生成树23programprim_example;Const vmax
7、=200var w:array[1..vmax,1..vmax]ofinteger; i,j,k,v,e:integer;procedureprim(v0:integer);{v0是开始结点} var flag:array[1..vmax]ofboolean; min,prevk,nextk:integer; begin fillchar(flag,sizeof(flag),false); flag[v0]:=true;{先选出v0} fori
