前言
最短路径是求在一张有向图中，起点到终点的距离。求最短路径的方法有很多，如SPFA、floyd、dijkstra等，今天我们学习dijkstra的思路与代码，其优点是时间复杂度和空间复杂度都很低，缺点是不能处理重边。

程序设计思路
dijkstra基于贪心实现，又有点类似DP，其思路大致如下：先把起点到所有点的距离都设为inf（一个很大的数），然后在所有与起点相连接的边中找到最短的一条，将这个新的点作为起点，并更新从起点出发到这个点的最短距离，直到找到终点。这个逐步更新的操作被称为松弛。

代码实现

洛谷上还有一道数据随机的模板题，这题专卡SPFA，但对我们的dijskla没有影响，下面是代码：

#include <bits/stdc++.h>
#define inf 2147483647
using namespace std;

struct Edge{//结构体用来存一条边的起点、终点、长度
    int to,dis,ne;
}edge[2000005];

int n,m,s,cnt,dist[2000005],head[2000005],x,y,z;//n、m、s如题意，cnt用来计数，dist存起点到各个点的最短距离
bool visit[2000005];//类似BFS中记录已经访问的点

void Add_edge(int from,int to,int w){//加入数组
    edge[++cnt].to=to;
    edge[cnt].dis=w;
    edge[cnt].ne=head[from];
    head[from]=cnt;
}

struct node{
    int id,dis;
    bool operator <(const node &a)const{ return a.dis<dis; }//优先队列升序排序
};
void dijkstra(){
    priority_queue<node> q;
    q.push(node{s,0});
    for(int i=1;i<=n;i++) dist[i]=inf;
    dist[s]=0;
    while(!q.empty()){
        node a=q.top();
        q.pop();//类似BFS的队列
        int now=a.id;
        if(visit[now]) continue;
        visit[now]=1;
        for(int i=head[now];i;i=edge[i].ne){//查所有边
            int j=edge[i].to;
            if(dist[now]+edge[i].dis<dist[j]){//判断走的这条路是不是比原来的更短
                dist[j]=dist[now]+edge[i].dis;
                q.push(node{j,dist[j]});
            }
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        Add_edge(x,y,z);
    }
    dijkstra();
    for(int i=1;i<=n;i++) printf("%d ",dist[i]);
    return 0;
}

结语
dijkstra不能处理重边，这一点在选择方法时需要注意。我是faryou，再见！

前言
最小生成树是指在一个无向图内，找出一棵树，使得各个结点之间能够互相到达，且总路径长度最短。

程序设计思路
最小生成树主要有两种思路——Kruskal和Prim，两者的时间复杂度为On2和On3，限于篇幅原因，故进行两者的讲解，只提供Kruskal的代码。
首先讲时间复杂度较高的Prim算法（有点像dijkstra）：在图中先确定一个点，将该点加入队列，之后每次循环在与队列中的所有点连接的边中找出最短边（不得与之前已经在队列中的点相连），直到所有的点都被加入队列。
Kruskal是一种基于贪心的算法：每次在所有的边中找出最短边，判断其两端有没有与之前已经相连的点重复，直到所有点之间都已连接。因此，Kruskal需要进行排序操作。

代码实现

这里只放Kruskal的代码：

#include <bits/stdc++.h>
struct tree{//存边，x、y分别代表两个端点，z为边权
    int x,y,z;
}tr[200005];

int n,m,iq,aq,sb=0,bin[5005],ans=0;//n、m如题意，iq、aq分别临时存放路径，sb用于计数（只拿n-1条边），bin存放每个点的路径，ans累加长度

int find(int a){//由于Kruskal基于树进行，可以使用路径压缩，详见并查集那篇文章
    int x=a;
    if(bin[x]!=x) return bin[x]=find(bin[x]);
    else return x;
}

bool cmp(tree a,tree b){//sort升序
    return a.z<b.z;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){//读入
        scanf("%d%d%d",&tr[i].x,&tr[i].y,&tr[i].z);
        bin[tr[i].x]=tr[i].x;
        bin[tr[i].y]=tr[i].y;
    }
    sort(tr+1,tr+m+1,cmp);//升序排序
    for(int i=1;i<=m;i++){//遍历每条边
        iq=find(tr[i].x);//找当前边的x是否连入图中
        aq=find(tr[i].y);//找当前边的y是否连入图中
        if(iq==aq) continue;//当两者祖先相同时，直接跳过防止成环
        ans+=tr[i].z;//累加
        sb++;//计次
        bin[aq]=iq;//修改路径
        if(sb==n-1) break;//当要取的边数量足够时，退出循环
    }
    for(int i=1;i<n;i++) if(find(i)!=find(i+1)){//判断每个点的祖先是否相同
        printf("orz");
        return 0;
    }
    printf("%d",ans);
    return 0;
}

这里需要注意的是，由于我们已经完成了排序，故不需要在之后判断大小。

结语
本文中讲了Kruskal的思路及代码，并融入了并查集的知识。我是faryou，再见！

前言
图论是算法中的一个重要内容，图的范围很广，包括二叉树、树、图等。今天我们来学习树的重要内容——并查集。

程序设计思路
并查集是一个森林（由一棵或多棵树组成的集）。我们可以利用其特性进行一些操作。
在并查集中，最重要的操作便是并和查。
并是指将两棵树合并为一棵。这很好进行，因为并查集里的每个数都有一个指针指向自己的父亲。
查找也不难，只需要一个递归程序，不断查找父亲的父亲，最后找到最老的祖先再返回（注意：并查集中最老的祖先的祖先是其自身）。
比较重要的是一个优化方案——路径压缩。由于查找是递归调用，故当要找的祖先过于遥远时，我们可以使用路径压缩，将一棵树中的全部非根节点的祖先直接设置为最老的祖先。路径压缩通常在执行查找命令时进行。

代码实现
下面通过并查集的模板题讲解其用法：

这题要求我们模拟并查集的操作，直接上代码：

#include <bits/stdc++.h>
using namespace std;

int n,m,z[200005],x[200005],y[200005],bin[10005];//z、x、y如题意，bin为并查集中每个数的祖先（父亲）

int find(int a){//查找操作
    int x=a;
    if(bin[x]!=x) return bin[x]=find(bin[x]);//在查找的过程中路径压缩
    else return x;//当查到某个数的祖先是它自己时，说明找到了祖先，开始返回
}
void join(int b,int c){//并操作
    if(find(b)!=find(c)) bin[find(b)]=find(c);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) bin[i]=i;
    for(int i=1;i<=m;i++) scanf("%d%d%d",&z[i],&x[i],&y[i]);
    for(int i=1;i<=m;i++){
        if(z[i]==1) join(x[i],y[i]);
        else{
            if(find(x[i])==find(y[i])) printf("Y\n");
            else printf("N\n");
        }
    }
    return 0;
}

这样，我们就较好的模拟了一个并查集。

结语
并查集是图论中较为简单的一科，只需要记下并、查两个操作就可以解决相关问题。我是faryou，再见！

前言
上一篇文章中我们学习了简单DP，今天我们来学习一种也很常见的DP——背包DP。

程序设计思路
背包DP以01背包和完全背包为基础，其他的背包DP都由这两种延伸出去，先看01背包：
01背包是最简单的背包DP，它是指有n样物品，第i样物品的价值为xi，所占用的容量为yi，你有一个容量为m的背包，要求你用这个背包装下价值最高的物品，每种物品只能装一次。这里每样物品的状态都只有装或不装。故我们可以列出状态转移方程：fi=max(fi-1,fi-1+xi（fi表示在第1到第i个物品中选容量为j的物品能获得的最多的价值）。
完全背包与01背包的区别在于它每样物品可以选无数次，但它的状态转移方程和01背包有不同。我们可以列出状态转移方程：fi=max(fi-1+k*xi)（这里的k是指购买了k件i物品，是for循环中的变量），这样做的时间复杂度为O(n3)，明显偏慢了。但是我们还有下面的优化：fi=max(fi-1,fi+xi)，因为我们在进行这次转移前就已经充分的考虑了。这个优化必须自己想清楚。

代码实现
来看一个01背包问题：

很明显，这是一道背包题。直接看代码：

#include <bits/stdc++.h>
int n,m,a[105],dp[105][1005];//n、m、a如题意，dp指上文中i

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){//分类讨论，判断能不能买
        if(j==a[i]) dp[i][j]=dp[i-1][j]+1;
        if(j>a[i]) dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
        if(j<a[i]) dp[i][j]=dp[i-1][j];
    }
    printf("%d",dp[n][m]);
    return 0;
}

DP注重的是自己的理解，而且讲解无法达到很好的效果，请自行理解源码~

结语
背包问题是DP中较为简单的一类，要想学好DP，就应该多刷题，以此总结经验。我是faryou，再见！

前言
上一篇文章中介绍了递推，其实也是为今天的DP打好基础。

程序设计思路
DP本质上就是对题目进行分类讨论，列出其不同情况下的状态转移方程，然后套上循环求解。
DP的种类有很多，其应用范围几乎涵盖了全部的算法内容，理论上来说，只要你有能力列出状态转移方程，DP可以解决几乎一切问题。今天我们讲一下简单的DP，了解一下DP的思路。

代码实现
由于DP的可拓展性太强，今天我破例用两道题进行讲解：

这道题要求我们得到最大的和。这里有一个思路：每次将金字塔底部相邻的两个数相比较，将大者加到这两个数正上方的数上。即：fx=max(fx,fx+1)+fx（金字塔存储为直角三角形）。下面是代码：

#include <bits/stdc++.h>
int r,f[1005][1005];//r如题意，f为DP用数组
int main(){
    scanf("%d",&r);
    for(int i=0;i<r;i++) for(int j=0;j<i+1;j++) scanf("%d",&f[i][j]);//读入数据
    for(int i=r-1;i>0;i--) for(int j=0;j<r-1;j++) f[i-1][j]+=max(f[i][j],f[i][j+1]);//递推式
    printf("%d",f[0][0]);//输出塔尖
    return 0;
}

这道题是经典动规题，我们通过层层上推求出结果。再来看下面这题：

本题初看没有思路，但是细细一想，一个长度为n的上升子序列可以分为前面长度为n-1的上升子序列和后面的一个数，那么我们可以先把所有f[x]都初始化为1，之后用双层循环（双指针），将后面的大数和前面的子序列拼为一个序列。由此，我们可以列出这样的方程：f[x]=max(f[i],f[j-1])（f[x]表示从第1到第x个数的最长上升子序列长度），下面是代码：

#include <bits/stdc++.h>
int n,ans=0,a[5005]={0},f[5005]={0};
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f[i]=1;
    }//以上为读入+初始化（一个数自己也算最长上升子序列）
    for(int i=1;i<=n;i++) for(int j=1;j<=i-1;j++) if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);//递推式，当找到一个更大的数时，将其加入前面的子序列
    for(int i=1;i<=n;i++) ans=max(ans,f[i]);//拿到最长长度
    printf("%d",ans);//输出
    return 0;
}

结语
其实DP本身的思路不难，关键在于你能不能找出所有情况。下篇文章，我将介绍背包DP。我是faryou，再见！