又好久好久没写题了。开学真的是有点忙，虽然我已经尽力在别的事情上甩锅，好自己安安静静地玩电脑了。
这期间，我大概从用 LaTeX 写了两篇作业之后再也受不了了，毕竟这是个排版工具，所见与所得差的远着呢，格式代码太多，根本无法专心于内容，想来，跟我的需求还是不符的。而 word 别说了，老师不强求我是不会用的，虽然所见即所得，这货还需要用鼠标搞格式，如果不想边写边挪开右手抡起鼠标调半天，就会很丑。于是挑选了一个导出 pdf 效果还不错的 markdown 编辑器。顺带发现很好用 ，抛弃了两栏这种用法，直接边写边渲染，导出的效果也还可以。
然后就继续用起了 matlab，这是作业要求，而且现在也不是那么嫌弃 matlab 的语言了，毕竟我发现现成的功能非常强大，如果能认真读读 help 文档，多搜一搜，用好内部的函数，一句一句还是非常好看的。作为工具，确实是非常优秀的。
agrinet：最小生成树的 Prim 算法
AC代码如下，全部 0.00secs 通过。
#include <cstdio>
#include <cstdlib>
#define INF (1 << 30)
int main(){
FILE *fin = fopen("agrinet.in", "r");
FILE *fout = fopen("agrinet.out", "w");
const int maxN = 100;
int N, conn[maxN][maxN];
int dist[maxN]; //min dist to any vertices in the tree
bool in[maxN]; //whether the vertices is in tree
fscanf(fin, "%d", &N);
for(int i = 0; i < N; i ++){
for(int j = 0; j < N; j ++){
fscanf(fin, "%d", &(conn[i][j]));
}
}
for(int i = 0; i < N; i ++){
dist[i] = conn[0][i];
in[i] = false;
}
in[0] = true;
dist[0] = 0;
int closest, minDist;
for(int i = 1; i < N; i ++){ //每次添加一个vertice，循环 N - 1次
//找到距离树最近的点
minDist = INF;
for(int j = 0; j < N; j ++){
if(!in[j] && minDist > dist[j]){
closest = j;
minDist = dist[j];
}
}
//加入树中
in[closest] = true;
//更新其邻居
for(int j = 0; j < N; j ++){
if(!in[j] && conn[closest][j] < dist[j]){
dist[j] = conn[closest][j];
}
}
}
int sumDist = 0;
for(int i = 0; i < N; i ++){
sumDist += dist[i];
}
fprintf(fout, "%d\n", sumDist);
return 0;
}
算法很简单。dist[]存的是顶点到现有树的距离。对于已经在树中的顶点，这个就是它和父节点之间的距离，也就是一条边。等到生成树建立后，求和即是树的最短长度。再用一个in[]标记每个顶点是不是在树中了。
拿到距离矩阵后，选第一个点在树中，对其邻居更新 dist 为它与第一个点之间的距离，不邻接的点为 INF。
找到不在树中的 dist 最小的点，加入树中，同时，对它的没在树中的邻居，更新一下到树的距离。
重复直到所有顶点都在树中。
有点像 dijkstra
我一度以为自己看到的是 dijkstra。下面来自论文（我的天这还可以写论文？）
记所有顶点集合为 V，Prim 算法和 Dijkstra 算法均是将图中的顶点分为两部分，记所求的最小生成树或者单源最短路径的顶点集合为 U，每次都在 V - U 集合中选择一个顶点放入 U 中，这个顶点的边要求满足算法所定义的距离极小性，依次选择，直到 U == V 时停止添加，所得到的树就能代表最小生成树或是单源最短路径。
两个算法的区别主要是对顶点之间距离的定义不同，Prim 算法定义的距离是集合V - U 中的点与 U 中点所确定边的最小权值，而 Dijkstra 算法定义的距离是源点到其他点的直接到达路径与通过中间点到达的路径的最小权值。
证明
连证明也是一个套路的，除了反证之外，我也没办法了，而且根本想不到作者这脑子怎么想到的这个算法。证明来自某个大神的博客。
反证法：假设prim生成的不是最小生成树
1).设prim生成的树为G0
2).假设存在Gmin使得cost(Gmin)<cost(G0) 则在Gmin中存在<u,v>不属于G0
3).将<u,v>加入G0中可得一个环，且<u,v>不是该环的最长边(这是因为<u,v>∈Gmin)
4).这与prim每次生成最短边矛盾
5).故假设不成立，命题得证.
网友评论