Today is Friday.
Today is poor.
Today 是拿到Blog账号的第一天，我也是在老师的要求下写了这篇绝世之作（我是十分不愿意的）
At today afternoon.
我们讲了图论的基本知识
图论的基本知识：
(a)有向图：图的边有方向，只能按箭头方向从一点到另一点。
(b)无向图：图的边没有方向，可以双向。
结点的度：无向图中与结点相连的边的数目，称为结点的度。
结点的入度：在有向图中，以这个结点为终点的有向边的数目。
结点的出度：在有向图中，以这个结点为起点的有向边的数目。
权值：边的“费用”，可以形象地理解为边的长度。
连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V 是连通的。
回路：起点和终点相同的路径，称为回路，或“环”。
完全图：一个n 阶的完全无向图含有n*(n-1)/2 条边；一个n 阶的完全有向图含有n*(n-1)条边；
稠密图：一个边数接近完全图的图。
稀疏图：一个边数远远少于完全图的图。
强连通分量：有向图中任意两点都连通的最大子图。
和最短路径算法之一的“Floyd”算法(求任意两点之间的距离）。在我看来这个算法就是暴力循环。一个个的去枚举。
“Floyd”算法具体思想如下：
a[i][j]表示为i到j的最短距离
有一个数组如下：
0 5 8 ∞ 3
5 0 2 ∞ 6
8 2 0 10 4
∞ ∞ 10 0 11
3 6 4 11 0
其中数字表示i到j的距离，‘∞’（也可以设为999999）表示i无法直接到j
我们假设i到j的距离不只是直接到达，而是有经过另外一些点，再到j点。
k从1开始，一直到n。表示i经过k到j
方程如下：
if(a[i][j]>a[i][k]+a[k][j])
{
a[i][j]=a[i][k]+a[k][j];
}
或
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
等k遍历完后,a[i][j]就表示为i到j的最短距离
具体代码如下：
for(int k=1;k<=m;k++)
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
}
}
Path数组初始化
for(int i=1;i<=n;i++)
｛
for(int j=1;j<=n;j++)
｛
if(e[i][j]<inf && i!=j)
path[i][j]=i;
else
path=-1;
｝
｝
总的来说今天讲的知识还是比较好理解的
应该是比明天的简单很多的
But图论的题丝毫不简单
我没打多少题
Come on tomorrow