2.28-3.2 学习记录（复习最小生成树,矩阵快速幂）

1.知识点复习：并查集，最小生成树(prime和克鲁斯卡尔)算法.
并查集

void init(int x)//初始化
{
    for(int i=1;i<=x;i++)
    {
        f[i]=i;
        rank[i]=1;
    }
 } 
int find(int x)
{
    if(x==f[x])
    return x;
    else {//路径压缩
        f[x]=find(f[x]); 
        return f[x];
    }
    /*非路径压缩
    else{
    return find(f[x]);
        }
    */
}
//按序合并 
void merge(int x,int y)
{
    int n=find(x),m=find(y);
    if(rank[n]==rank[m]) {
        f[m]=n;rank[n]++;
    }
    if(rank[n]>rank[m]){
        f[m]=n;
    }
    else f[n]=m;
}
//按序合并与路径压缩一般不一起用。
void merge1(int x,int y)
{
    int n=find(x),m=find(y);
    f[n]=m;
 } 

克鲁斯卡尔算法写最小生成树要用到并查集(数据大时一定要用路径压缩)。

prime算法模板

int prime(int n,int st)
{
    int cnt=st;
    vis[st]=1;//标记起点并记录他 
    for(int i=1;i<=n;i++)
    {
        if(i==st) dis[st]=0;
        else dis[i]=mp[i][st];
    }
    //更新dis
    for(int i=1;i<n;i++)//再找接下来的n个点 
    {
        int mini=min_n;
        for(int j=1;j<=n;j++)//找到目前未归类的最短路径连接的点
        {
            if(vis[j]==0&&mini>dis[j])
            {
                mini=dis[j];
                cnt=j;
            }
         }
        ans+=dis[cnt];
        vis[cnt]=1;
        for(int j=1;j<=n;j++)//更新路径 
        if(vis[j]==0&&dis[j]>mp[cnt][j])//以目前找到的点为起点更新dis 
            dis[j]=mp[cnt][j];
                                /*迪杰斯特拉
                                if(vis[j]==0&&dis[j]>mp[cnt][j]+dis[cnt])
                                dis[j]=mp[cnt][j]+dis[cnt];
                                */
    }
 } 

由于prime算法与迪杰斯特拉思路相似，重新写一下思路复习两个算法。将已经连接的点与未连接的点设定两个集合，用vis[ ]数组标记是否找到，vis[]=1表示找到。每次从vis[]=0的集合里找到一个距离vis[]=1集合最近的点，并更新dis[].迪杰斯特拉与prime算法的不同处就在于更新dis的操作。
用线段树完成动态最小生成树