文章列表
题目大意：给定一个无向图加权图，求给定的两点间可经过的路径的最大边权最小。
题目分析：这是Floyd算法的变形，设d[i][j]:表示从i到j所经过的最大权值的最小值
状态转移方程：d[i][j]=min{max{d[i][k],d[k][j]},d[i][j]},利用Floyd算法改
变状态转移部分的代码即可AC。
//Uva 10048 - Audiophobia
//多源最短路的变形
//d[i][j]:表示从i到j所经过的最大权值的最小值
//状态转移方程：d[i][j]=min{max{d[i][k],d[k][j]},d[i][j]},要求(i,k),(k,j) ...
题目大意：给定n(0<n<=100)个点，用线把这n个点连起来，使得任意两点间均可达
题目分析：很明显，基本最少生成树问题。a[i][j],表示点i,j之间的距离，由于是稠密图，所以采用Prim算法。
//Uva 10034 - Freckles
//最小生成树问题，采用Prim算法
#include <iostream>
#include <cmath>
#include <cstdio>
#include <memory.h>
#define eps 1e-6
using namespace std;
c ...
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=508
题目大意：给定20个点，以及一些连接这些点的边，然后多次任意给定两点，求起始点到终点所经过的最少边数。
题目分析：此题可以把图看作是一个所有权值均为1的带权无向图，即求任意顶点之间的最短路问题，用Floyd算法。
由于此题的数据量很少，所以直接用bfs也可。
代码：
//权值均为1的多源最短路问题
//可以用bfs,由 ...