做宣传册网站网店推广方案范文

最短路

题目

903. 昂贵的聘礼

思路

如何建图：

1. 对于每一个物品，建立一条由虚拟源点指向该物品的边
2. 对于可以替换的物品，建立一条替换物品到目标物品的边

最终就是求虚拟源点到终点 $1$ 的边

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int g[N][N], dist[N];
bool st[N];
int level[N];
int ans = INF;void dijkstra(int l, int r)
{memset(st, false, sizeof st);memset(dist, 0x3f, sizeof dist);dist[0] = 0;// 因为多了一个虚拟源点0，所以要循环n+1次for(int i = 0; i <= n; i ++ ) {int t = -1;for(int j = 0; j <= n; j ++ ) // 还有虚拟源点 0if(!st[j] && (dist[j] < dist[t] || t == -1)) t = j;st[t] = true;if(t && (level[t] < l || level[t] > r)) // 特判虚拟源点continue;for(int j = 1; j <= n; j ++ ){if(level[j] < l || level[j] > r)    continue;dist[j] = min(dist[j], dist[t] + g[t][j]);}}ans = min(ans, dist[1]);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);memset(g, 0x3f, sizeof g);for(int i = 0; i < N; i ++ ) g[i][i] = 0;cin >> m >> n;for(int i = 1; i <= n; i ++ ){int price, k;cin >> price >> level[i] >> k;g[0][i] = price;while(k -- ){int b, c;cin >> b >> c;g[b][i] = c;}}for(int i = level[1] - m; i <= level[1]; i ++ ) dijkstra(i, i + m);cout << ans << endl;return 0;
}

BFS

题目

矩阵距离
给定一个由 $0$, $1$ 构成的矩阵，让我们求每一个$0$ 到 $1$ 的最短哈密顿距离。

思路
由题目描述，所有 $1$ 的位置到 $1$ 的最短哈密顿距离为 $0$，然后把所有 $1$ 加入队列，这样每一个 $0$ 第一次入队的距离就是最短的。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;typedef pair<int, int> PII;const int N = 1010;int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int a[N][N], b[N][N];
bool st[N][N];void bfs()
{memset(b, 0x3f, sizeof b);memset(st, false, sizeof st);queue<PII> q;//<==> 建立虚拟源点for(int i = 0; i < n; i ++ )for(int j = 0; j < m; j ++ )if(a[i][j] == 1){q.push({i, j});st[i][j] = true;b[i][j] = 0;}while(q.size()){auto t = q.front();q.pop();for(int i = 0; i < 4; i ++ ){int x = t.first + dx[i], y = t.second + dy[i];if(x < 0 || x >= n || y < 0 || y >= m || st[x][y] || a[x][y])  continue;b[x][y] = b[t.first][t.second] + 1;q.push({x, y});st[x][y] = true;}}
}int main()
{cin >> n >> m;for(int i = 0; i < n; i ++ ){string s;   cin >> s; //由于题目给定的数据之间没有空格，最好是直接读入一个字符串for(int j = 0; j < m; j ++ )    a[i][j] = s[j] - '0';}bfs();for(int i = 0; i < n; i ++ ){for(int j = 0; j < m; j ++ )   cout << b[i][j] << ' ';cout << endl;}return 0;
}

最短路

题目

选择最佳路线
题目让我们求多起点，单一终点的最短路

思路
我们是无法在一次最短路中求出多个起点到单一终点的最短距离的。
除非使用 $Floyd$ 算法，但时间复杂度不支持。

一、虚拟源点
把所有起点由一个虚拟源点连接起来，那么题目就转化成了求一个虚拟源点到单一终点的最短距离。
下面的代码是虚拟源点做法。

二、反向建图
题目让我们求多个起点到单一终点的最短的一条路径，我们可以反向建图，求单一终点所有起点中的距离的最小值。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;typedef pair<int, int> PII;// M = 20010 会出错
const int N = 1010, M = 21010, INF = 0x3f3f3f3f;int n, m, S, cnt;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}int dijkstra()
{memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);priority_queue<PII, vector<PII>, greater<PII> > q;q.push({0, 0});dist[0] = 0;while(q.size()){auto t = q.top();q.pop();int ver = t.second, distance = t.first;if(st[ver]) continue;st[ver] = true;for(int i = h[ver]; i != -1; i = ne[i]){int j = e[i];if(dist[j] > distance + w[i]){dist[j] = distance + w[i];q.push({dist[j], j});}}}return dist[S];
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);while(cin >> n >> m >> S){memset(h, -1, sizeof h);idx = 0;while (m -- ){int a,  b, c;cin >> a >> b >> c;add(a, b, c);}cin >> cnt;while(cnt -- ){int x;  cin >> x;add(0, x, 0);}int t = dijkstra();if(t == INF)    t = -1;cout << t << endl;}return 0;
}

最小生成树

题目

新的开始
题目说明该图可能存在多个联通块，求这些连通块的最小生成树之和

思路
因为我们在每个连通块中都需要设置一个起点（$dist[S]=0$），所以说这题就是一个多起点问题，多起点就要立马想到虚拟源点。
由于我们设置了一个虚拟源点，那么点数就会多 $1$，所以在求最小生成树的时候，循环次数也要加 $1$。

代码

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 310;int n;
int g[N][N];
int dist[N];
bool st[N];int prim()
{memset(dist, 0x3f, sizeof dist);dist[0] = 0;int res = 0;for(int i = 0; i <= n; i ++ ){int t = -1;for(int j = 0; j <= n; j ++ )if(!st[j] && (t == -1 || dist[j] < dist[t]))    t = j;st[t] = true;res += dist[t];for(int j = 0; j <= n; j ++ )   dist[j] = min(dist[j], g[t][j]);}return res;
}int main()
{memset(g, 0x3f, sizeof g);for(int i = 0; i < N; i ++ )    g[i][i] = 0;cin >> n;for(int i = 1; i <= n; i ++ )   {int x;  cin >> x;g[0][i] = g[i][0] = x;}for(int i = 1; i <= n; i ++ )for(int j = 1; j <= n; j ++ )cin >> g[i][j];cout << prim() << endl;return 0;
}

总结

起点和终点划分最短路

单一起点，多个（单一）终点：（普通单源最短路）

多个起点，单一终点

1. 反向求最短路，转化为单一起点，多个终点
2. 创建虚拟源点，转化为单一起点，单一终点最短路。

多个起点，多个终点

1. 创建虚拟源点，转化成单一起点，多个终点最短路
2. 创建虚拟汇点，转化为多个起点，单一终点最短路，然后反向求最短路

区分这里的多起点多终点的含义：在起点的集合和终点的集合中各选取一个起点和终点的最短路径，并不是让我们求每个起点到每个终点的最短路径。

细节问题

由于我们在创建虚拟源点或者虚拟汇点的时候，需要额外的边用来连接虚拟源点，所以边数需要多开 $N$ 条边。