四、简单图论
1、单源最短路径
Dijkstra算法：求解边权均为正的单源最短路。
朴素版本：适用于稠密图（边数和点数平方一个数量级）
代码模板
int n; //点数
int g[N][N]; //邻接矩阵存储图
int dist[N]; //存储每个点到1号点的最短距离
bool st[N]; //存储每个点的最短路是否已经确定
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<n;i++){ //迭代n次
int t=-1;
for(int j=1;j<=n;j++){ //寻找距离最小的点
if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
}
st[t]=true; //标记为已确定
for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]); //用距离最小的点来更新其他点距离1号点的距离
}
if(dist[n]==0x3f3f3f3f) return -3; //最短路不存在
else return dist[n]; //存在直接返回
}
选看:
堆优化Dijkstra算法：适用于稀疏图（边数和点数一个数量级）可以参考我的该篇博客
Spfa算法：求解存在负权边的最短路。
代码模板
int n,m; //n表示点数，m表示边数
int h[N],e[M],ne[M],w[M],idx; //邻接表存储图
int dist[N]; //存储每个点到1号点的最短距离
bool st[N]; //存储每个点是否已经在队列中
//邻接表加边
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int spfa(){
memset(dist,0x3f,sizeof dist);
queue<int> q;
dist[1]=0;
st[1]=true;
q.push(1);
while(!q.empty()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
if(dist[n]==0x3f3f3f3f) return -3;
else return dist[n];
}
参考例题：这里
2、多源最短路
注：若时间紧迫，优先记忆Floyd算法，也可解决单源最短路问题，只不过时间复杂度较高，可以用其获得部分分数。
Floyd算法：求解多源最短路。
代码模板
int n; //点数
int d[N][N]; //邻接矩阵存储图，算法结束后d[i][j]存储i、j之间的最短路径长度
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) d[i][j]=0;
else d[i][j]=0x3f3f3f3f;
}
}
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
//注意，若图中存在负权边，所以1号点无法到n号点，d[1][n]也可能被更新也可能则d[i][j]若大于0x3f3f3f3f/2即可认为最短路不存在
参考例题：这里
3、最小生成树
Prim算法：
代码模板
int n; //点数
int dist[N]; //存储点到当前最小生成树的距离
int g[N][N]; //邻接矩阵存储每条边
bool st[N]; //存储每个点是否已经在生成树中
int prim(){
memset(dist,0x3f,sizeof dist);
int res=0; //存储最小生成树边权重之和
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){ //寻找距离当前生成树最小的点
if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
}
if(i&&dist[t]==0x3f3f3f3f3) return 0x3f3f3f3f; //如果距离最小的点的距离仍然是正无穷说明无最小生成树
if(i) res+=dist[t];
for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
st[t]=true;
}
return res; //返回最小生成树边权重之和即可
}
Kruakal算法：
代码模板
int p[N]; //并查集父结点数组
int find(int x){ //并查集find操作
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
struct Edge{ //存储每条边
int a,b,w;
}edges[M];
bool cmp(Edge A,Edge B){ //手写cmp，使sort能为结构体排序
return A.w<B.w;
}
int kruskal(){
for(int i=1;i<=n;i++) p[i]=i; //初始化并查集
sort(edges,edges+m,cmp); //按边权从小到大排序
int res=0,cnt=0; //res记录最小生成树边权之和，cnt记录当前最小生成树种的边数
for(int i=0;i<m;i++){
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
if(find(a)!=find(b)){ //最小边权的起点和终点a,b不在一个连通块则合并他们
p[find(b)]=find(a);
res+=w;
cnt++;
}
}
if(cnt<n-1) return 0x3f3f3f3f; //n个点，最小生成树的边应为n-1条，少于n-1说明没有最小生成树
else return res;
}
参考例题：这里
五、动态规划
1、0-1背包
0-1背包问题：每件物品只有一个。
代码模板
int dp[N]; //存储每个状态的最大价值
int v[N],w[N]; //v[]存储每个物品的体积，w[]存储每个物品的价值
int n,m; //n为物品数，m为背包容积
for(int i=1;i<=n;i++){ //枚举每个物品
for(int j=m;j>=v[i];j--){ //逆序枚举背包体积
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
具体参考这里
2、完全背包
完全背包问题：每种物品有无限个。
代码模板
int dp[N]; //存储每个状态的最大价值
int v[N],w[N]; //v[]存储每个物品的体积，w[]存储每个物品的价值
int n,m; //n为物品数，m为背包容积
for(int i=1;i<=n;i++){ //枚举每个物品
for(int j=v[i];j<=m;j++){ //正序枚举背包体积
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
3、多重背包
多重背包问题：每种物品有不同数量。
代码模板
int dp[N]; //存储每个状态的最大价值
int v[N],w[N],s[N]; //v[]存储每个物品的体积，w[]存储每个物品的价值，s[]存储每个物品的最大数量
int n,m; //n为物品数，m为背包容积
for(int i=1;i<=n;i++){ //枚举每个物品
for(int j=m;j>=v[i];j--){ //逆序枚举背包体积
for(int k=0;k<=s[i]&&k*v[i]<=j;k++){
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
}
}
}
参考例题：这里
4、线性DP
DP没有固定模板，建议复习一下最长上升子序列和最长公共子序列问题的解题思想。
总结
以上内容均为比较基础的内容，如果学有余力，可以多拓展一些，真正的强者不应止步于此，我去写周赛题解了，再见。
最后希望我们都能取得自己心仪的成绩，我们一起加油，奥利给!
