各类算法汇总（补充中…）

dijkstra（单源最短路径）：

策略：

设集合S存放已被访问的顶点，然后执行n次下面的两个步骤

（1）每次从集合V-S（未访问节点）选择与起点s的距离最小的一个顶点（记为u），访问并加入集合S（已访问节点）。

（2）之后，令顶点u为中介点，优化起点s与所有从u能到达的顶点v之间的最短距离。

 复制代码
constint MAXV = 1000;//最大顶点数
constint INF = 0x3f3f3f3f;//设INF为一个很大的数
 
int n, G[MAXV][MAXV];//n为定点数，MAXV为最大定点数
int d[MAXV];//起点到各点的最短路径长度
bool vis[MAXV] = {false};//标记数组，vis[i]==true表示已访问。初值均为false
 
void Dijkstra(int s){//s为起点
    fill(d, d + MAXV, INF);//fill函数将整个d数组赋为INF(慎用memset)
    d[s] = 0;//起点s到达自身的距离为0
    for(int i = 0; i < n; i++){//循环n次
        int u = -1, MIN = INF;//u使d[u]最小，MIN存放该最小的d[u]
        for(int j = 0; j < n; j++){//
            if(vis[j] == false && d[j] < MIN){
                u = j;
                MIN = d[j];
            } 
        }
        //找不到小于INF的d[u],说明剩下的顶点和起点s不连通
        if(u == -1) return;
        vis[u] = true;//标记u为已访问
        for(int v = 0; v < n; v++){//从u出发能达到的所有顶点v，更新d[v]
            //如果v未访问&&u能到达v&&以u为中介点可以使d[v]更优
            if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]){
                d[v] = d[u] + G[u][v];//优化d[v]
            }
        }
    }
}

图的DFS（求联通分量数）：

①邻接矩阵

 复制代码
const int MAXV = 1000;//最大顶点数
const int INF = 0x3f3f3f3f;//设INF为一个很大的数
 
int n, G[MAXV][MAXV];//n为定点数，MAXV为最大定点数
bool vis[MAXV] = {false};//如果顶点i已被访问，则vis[i]==true。初值为false
 
void DFS(int u, int depth) {//u为当前访问的顶点标号，depth为深度
    vis[u] = true;//设置u已被访问
    //如果需要对u进行一些操作，可以在这里进行
    //下面对所有从u出发能到达的分支进行枚举
    for (int v = 0; v < n; v++) {//对每个顶点v
        if (vis[v] == false && G[u][v] != INF) {//如果v未被访问，且u可达v
            DFS(v, depth + 1);//访问v，深度加1
        }
    }
}
 
void DFSTrace(){//遍历图G
    for(int u = 0; u < n; u++){//对每个顶点u
        //int count=0//用来统计联通分量数
        if(vis[u] == false){//如果u未被访问
            DFS(u, 1);//访问u和所在的连通块，1表示初始为1层
            //count++;
        }
    }
}

②邻接表

 复制代码
vector<int> Adj[MAXV];//图G的邻接表
int n;//n为定点数，MAXV为最大顶点数
bool vis[MAXV] = { false };//如果顶点i已被访问，则vis[i]==true，初值为fales
 
void DFS(int u, int depth) {//u为当前访问的顶点标号，depth为深度
    vis[u] = true;//设置u已被访问
    /*如果需要对u进行一些操作，可以在此处进行*/
    for (int i = 0; i < Adj[u].size(); i++) {//对从u出发可以到达的所有顶线v
        int v = Adj[u][i];
        if (vis[v] == false) {//如果v未被访问
            DFS(v, depth + 1);//访问v，深度加1
        }
    }
}
 
void DFSTrave() {//遍历图G
    for (int u = 0; u < n; u++) {//对每个顶点u
        if (vis[u] == false) {//如果u未被访问
            DFS(u, 1);//访问u和u所在的连通块，1表示初始为第一层
        }
    }
}

图的BFS

 复制代码
int n, G[MAXV][MAXV];//n为顶点数，MAXV为最大顶点数
bool inq[MAXV] = { false };//若顶点i曾入过队列，则inq[i]==true，初值为false
 
void BFS(int u) {//遍历u所在的连通块
	queue<int> q;//定义队列q
	q.push(u);//将初始点u入队
	inq[u] = true;//设置u已被加入过队列
	while (!q.empty()) {//只要队列非空
		int u = q.front();//取出队首元素
		q.pop();//将队首元素出队
		for (int v = 0; v < n; v++) {
			//如果u的邻接点v未曾加入过队列
			if (inq[v] == false && G[u][v] != INF) {
				q.push(v);//将v入队
				inq[v] = true;//标记v已被加入过队列
			}
		}
	}
}
 
void BFSTrave() {//遍历图G
	for (int u = 0; u < n; u++) {//枚举所有顶点
		if (inq[u] == false) {//如果u未曾加入过队列
			BFS(u);//遍历u所在的连通块
		}
	}
}

01背包：

递推：

dp[i][v]表示前i件物品（1≤i≤n,0≤v≤V）恰好装入容量为v的背包中所能获得的最大价值。

考虑对i件物品的选择策略:

1、不放第i件物品，那么问题转化为前i-1件物品恰好装入容量为v的背包中所能获得的最大价值，也即dp[i-1][v]

2、放第i件物品，那么问题转化为前i-1件物品恰好装入容量为v-w[i]的背包中所能获得的最大价值，也即dp[i-1][v-w[i]]+c[i]

$d p [i] [v] = m a x {d p [i - 1] [v], d p [i - 1] [v - w [i]] + c [i]}$

$(1 \leq i \leq n, w [i] \leq v \leq V)$

滚动数组：

$d p [j] = m a x {d p [j], d p [j - w [i]] + c [j]}$

 复制代码
#include<cstdio>
#include<algorithm>
using namespace std;
 
const int maxn = 100;//物品最大件数
const int maxv = 1000;//V的上限
 
int w[maxn], c[maxn], dp[maxv];
int main() {
    int n, V;
    cin >> n >> V;
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    //边界
    for (int v = 0; v < V; v++) {
        dp[v] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int v = V; v >= w[i]; v--) {
            //状态转移方程
            dp[v] = max(dp[v], dp[v - w[i]] + c[i]);
        }
    }
    //寻找dp[0...V]中最大的即为答案
    int max = 0;
    for (int v = 0; v <= V; v++) {
        if (dp[V] > max) {
            max = dp[v];
        }
    }
    cout << max;
}

完全背包

区别于01背包，每种物品都有无穷件。

dp[i][v]表示前i件物品（1≤i≤n,0≤v≤V）恰好装入容量为v的背包中所能获得的最大价值。

递推：

考虑对i件物品的选择策略:

1、不放第i件物品，那么dp[i][v]=dp[i-1][v],这步和01背包是一样的。

2、放第i件物品，不同于01背包，而是转移到dp[i][v-w[i]]，这是因为每种物品可以放任意件（注意有容量限制，因此还是有限的），放了第i件物品后还可以继续放第i件物品，直到第二维的v-w[i]无法保持大于等于0为止。

$d p [i] [v] = m a x {d p [i - 1] [v], d p [i] [v - w [i]] + c [i]}$

$(1 \leq i \leq n, w [i] \leq v \leq V)$

边界： $d p [0] [v] = 0 (0 \leq v \leq V)$

状态转移方程：

$d p [j] = m a x {d p [j], d p [j - w [i]] + c [j]}$

形成一维后和01背包完全相同，唯一的区别在于这里v的枚举顺序是正向枚举。

最小生成树：

prim算法：

 复制代码
using namespace std;
 
const int MAXV = 1000;//最大顶点数
const int INF = 100000000;//设INF为一个很大的数
 
int n, G[MAXV][MAXV];//n为顶点数，MAXV为最大顶点数
int d[MAXV];//顶点与集合S的最短距离
bool vis[MAXV] = { false };//标记数组，vis[i]==true表示已访问。初值均为false
 
int prim() {//默认0号为初始点，函数返回最小生成树的边权之和
    fill(d, d + MAXV, INF);//fill函数将整个d数组赋为INF(慎用memset)
    d[0] = 0;//只有0号顶点到集合S的距离为0，其余全为INF
    int ans = 0;//存放最小生成树的边权之和
    for (int i = 0; i < n; i++) {//循环n次
        int u = -1, MIN = INF;//u使d[u]最小，MIN存放该最小的d[u]
        for (int j = 0; j < n; j++) {//找到未访问的顶点中的d[]最小的
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        //找不到小于INF的d[u],则剩下的顶点和集合S不连通
        if (u == -1)return -1;
        vis[u] = true;//标记u为已访问
        ans += d[u];//将与集合S距离最小的边加入最小生成树
        for (int v = 0; v < n; v++) {
            //v未访问&&u能到达v&&以u为中介点可以使v离集合S更近
            if (vis[v] == false && G[u][v] != INF && G[u][v] < d[v]) {
                d[v] = G[u][v];//将G[u][v]赋值给d[v]
            }
        }
    }
    return ans;//返回最小生成树的边权之和
}