今天上午复习了一下图论中最小生成树和并查集有关的题目，做了练习中两个关于最小生成树的题目，两个题目都是标准的模板题，第一个题目顺利通过，但第二个题由于cin的速度过慢，所以一开始并未顺利ac，究于是否是算法出了问题，我又用prim算法敲了一次，结果也是未ac，最终换成scanf之后两个代码均顺利ac。虽然浪费了大量的时间，但对于代码的模板起到了一定的熟悉作用，下面总结一下两种算法:
对于prim算法：
这个算法的思路有点贪心的意味，大致思路是以一个点为起点，这个点所能到达的点进行一次检索，然后取路径权值最小的一个点为下一个点进行更新，一共更新n次，找到n个点，然后权值相加就是最小生成树的最小路径值和。
这种算法的模板是：
需要三个数组：
int minn[101];//储存到达的最小边权
bool fun[101];//储存是否访问过这个点
int a[101][101];//储存边权（从i到j）
memset (fun,0,sizeof(fun);
memset (minn,0x7f,sizeof(minn);//把初始边权变为一个很大的数字
minn[1]=0;//以1为起点开始查找
for (i=1;i<=n;i++){
x=0;
for (j=1;j<=n;j++){
if (!fun[j]&&minn[j]<minn[x]){//找下一个边权较小的点
x=j;
}
}
fun[x]=1;//标记x为下一个起点
for (j=1;j<=n;j++){
if (!fun[j]&&minn[j]<a[x][j]){//更新可到达的边权为最小值
minn[j]=a[x][j];
}
}
}
这段代码结束后，minn中储存的便是最小生成树的所有边的边权。
对于涉及到并查集查找方案kusckal算法，则是利用贪心和合并的原理，每次找边权最小的边，看看该边连接的两个点是否属于同一个“祖宗”，也就是是否已经连通，如果是，则进行下一次查找，如果不是，则合并两个边，边权加入总的边权中。一共寻找n-1次，得到一个最小生成树。
这种算法的模板是：
struct point {
int s;
int e;
int v;
}p[9901];//用结构体存边
fa[101];//用数组存放每个点的“祖宗”
int father(int x){
if (fa[x]!=x)fa[x]=father(fa[x]);
return fa[x];
}//并查集专用找“祖宗”代码。。。
void together(int x,int y){
int f1=father(x);
int f2=father(y);
if (f1!=f2){
fa[f1]=f2;
}//"祖宗"的合并，表示其二者属于同一个连通区域
sort(p+1，p+m+1,cmp);
for (i=1,x=0;i<=m;i++){
if (father(p[i].x)!=father(p[i].y)){
together(p[i].x,p[i].y);
total+=p[i].v;
x++;
}
if (x==n-1)break;
}
算法结束后total存的便是最小生成树的最小路径边权和。
下午的比赛做的有些迷迷糊糊，近几日光做搜索了，导致一见到题就想搜，结果理解错了题意，最后理解题意之后快速ac，虽然ac了，可还是浪费了大量的时间在一个假的题意上，可见快不是做题的目的， 理解了比什么都快。
明天的训练决定开始对最短路径算法的复习，然后悉数开始做图论的题。