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]
$$ dp[i][v]=max\left\{dp[i-1][v],dp[i-1][v-w[i]]+c[i]\right\}$$
$$(1\le i \le n ,w[i]\le v\le V)$$
滚动数组：
$$ dp[j]=max\left\{dp[j],dp[j-w[i]]+c[j]\right\} $$
#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为止。
$$ dp[i][v]=max\left\{dp[i-1][v],dp[i][v-w[i]]+c[i]\right\}$$
$$(1\le i \le n ,w[i]\le v\le V)$$
边界：$dp[0][v]=0(0\le v\le V)$
状态转移方程：
$$ dp[j]=max\left\{dp[j],dp[j-w[i]]+c[j]\right\} $$
形成一维后和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;//返回最小生成树的边权之和
}
最新评论