1.调度区间，P42
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<algorithm> using namespace std; typedef long long ll; const int MAX_N = 100000; // 区间总数 int n; // 存储输入的工作区间 int S[MAX_N], T[MAX_N]; // 存储工作区间 pair<int,int> it[MAX_N]; void solve() { for(int i = 0; i < n; i++){ it[i].first = T[i]; it[i].second = S[i]; } sort(it, it+n); int ans = 0, t = 0; for(int i = 0; i < n; i++){ if(t < it[i].second){ ans++; t = it[i].first; } } printf("ans = %d", ans); } int main() { cin >> n; for(int i = 0; i < n; i++){ cin >> S[i] >> T[i]; } solve(); return 0; }2.字典序最小问题
注意：这个算法处理左右两边有相同字符的情况非常精妙！
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<algorithm> using namespace std; typedef long long ll; const int MAX_N = 2000; //长度 int n; //字符串 char S[MAX_N+10]; void solve() { int a = 0, b = n - 1; while (a <= b) { bool left = false; for (int i = 0; a + i <= b; i++) { if (S[a + i] < S[b - i]) { left = true; break; } if (S[a + i] > S[b - i]) { left = false; break; } } if (left) putchar(S[a++]); else putchar(S[b--]); } putchar('\n'); } int main() { cin >> n; for(int i = 0; i < n; i++){ cin >> S[i]; } solve(); return 0; }Saruman’s Army
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<algorithm> using namespace std; typedef long long ll; const int MAX_N = 1000; // 点的位置，覆盖半径 int n, r; // 每个点的位置 int X[MAX_N+10]; void solve() { int i = 0, ans = 0; while (i < n) { int s = X[i++]; while(i < n && X[i] <= s+r) i++; int p = X[i - 1]; while(i < n && X[i] <= p+r) i++; ans++; } printf("ans = %d", ans); } int main() { cin >> n >> r; for(int i = 0; i < n; i++){ cin >> X[i]; } solve(); return 0; }Fence Repair
思路比较简单：找两块最短的版拼在一起，然后加入板集合，不断重复，直到最后只剩一块板。
需要注意的是算法实现找两块最小板的过程以及对mp1,mp2进行swap的操作
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<algorithm> using namespace std; typedef long long ll; // 上限 const int MAX_N = 20100; // 板的总数 int N; // 每块板的长度 int L[MAX_N+10]; void solve() { ll ans = 0; // 直到只有一块板为止 while(N > 1) { int mp1 = 0, mp2 = 1; if(L[mp1] > L[mp2]) swap(mp1, mp2); // 找出最小的两块板子 for(int i = 2; i < N; i++) { if (L[i] < L[mp1]) { mp2 = mp1; mp1 = i; } else if (L[i] < L[mp2]) { mp2 = i; } } int t = L[mp1] + L[mp2]; ans += t; if (mp1 == N-1) swap(mp1, mp2); L[mp1] = t; L[mp2] = L[N-1]; N--; } printf("ans = %d", ans); } int main() { cin >> N; for(int i = 0; i < N; i++){ cin >> L[i]; } solve(); return 0; }最长公共子序列（LCS）
LCS：Lonest Common Subsequence
i：s1串的前i个字符 j：s2串的前j个字符 dp[ i ][ j ]：代表s1串的前i个字符构成的串和s2串的前j个字符构成的串的最长公共子序列。
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<algorithm> using namespace std; typedef long long ll; // 字符串长度上限 const int MAX_N = 1050; // 两个字符串的长度 int n, m; // 两个字符串 string s1, s2; // dp数组 int dp[MAX_N][MAX_N] = {0}; // 状态转移方程 // if(s1[i] == s2[j]) // dp[i][j] = dp[i-1][j-1] + 1; // else // dp[i][j] = max(dp[i-1][j], dp[i][j-1]); void solve() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } printf("ans = %d", dp[n][m]); } int main() { cin >> n >> m; cin >> s1 >> s2; memset(dp, 0, sizeof dp); solve(); return 0; }01背包
思路：主要找到dp[ i ][ j ]中i，j对应的意思。 i：代表第i个物品。 j：代表目前可用容量为j。 dp[ i ][ j ]就代表的从第0到i个物品中挑选总重小于j时，总价值的最大值。
然后找到状态转移方程，就好求解了。 时间复杂度 O(NW)
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<algorithm> using namespace std; typedef long long ll; // 物品总数上限 const int MAX_N = 110; const int MAX_W = 10010; // 物品总数 int N; // 重量上限 int W; // 每个物品的重量和价格 int w[MAX_N], v[MAX_N]; // dp数组 int dp[MAX_N][MAX_W] = {0}; // if(j >= w[i]) // 状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]) // else // dp[i][j] =dp[i-1][j]; void solve() { for (int i = 1; i <= N; i++) { for (int j = 0; j <= W; j++) { if (j < w[i]) { dp[i][j] = dp[i-1][j]; } else { dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]); } } } printf("ans = %d", dp[N][W]); } int main() { cin >> N >> W; for(int i = 1; i <= N; i++){ cin >> w[i] >> v[i]; } memset(dp, 0, sizeof dp); solve(); return 0; }注意：使用memset对数组进行初始化时，初始值只能为0或者-1。
完全背包问题
在01背包的基础上增加了一个物品可以选多个的条件。
只需要调整状态转移方程即可。
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<algorithm> using namespace std; typedef long long ll; // 物品总数上限 const int MAX_N = 110; const int MAX_W = 10010; // 物品总数 int N; // 重量上限 int W; // 每个物品的重量和价格 int w[MAX_N], v[MAX_N]; // dp数组 int dp[MAX_N][MAX_W] = {0}; // 状态转移方程 // if(j >= w[i]) // dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i]) // else // dp[i][j] =dp[i-1][j]; void solve() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= W; j++) { if (j < w[i]) { dp[i][j] = dp[i-1][j]; } else { dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i]); } } } printf("ans = %d", dp[N][W]); } int main() { cin >> N >> W; for(int i = 1; i <= N; i++){ cin >> w[i] >> v[i]; } memset(dp, 0, sizeof dp); solve(); return 0; }01背包和完全背包也可以不断使用一个数组来实现。
此处思路很精妙，j 反向循环时： dp[ j ] = max(dp[ j ], dp[ j - w[ i ]]+v[ i ]) 相当于使用二维数组时的 dp[ i ][ j ] = max(dp[ i - 1][ j ], dp[ i ][ j - w[ i ]]+v[ i ]) 此时dp[ j ]的值就是选择i-1个物品总重量在j以内的最大价值； dp[ i ][ j - w[ i ]]+v[ i ])表示选择当前物品的能够得到的最大价值 即为01背包。
j 正向循环时： dp[ j ] 状态转移方程中使用到的是已经被更新过的 dp[ j - w[ i ]]+v[ i ]，就会记录选了一个，两个，或者三个当前物品后的最大价值。 所以为完全背包。
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<algorithm> using namespace std; typedef long long ll; // 物品总数上限 const int MAX_N = 110; const int MAX_W = 10010; // 物品总数 int N; // 重量上限 int W; // 每个物品的重量和价格 int w[MAX_N], v[MAX_N]; // dp数组 int dp[MAX_W] = {0}; // 状态转移方程 // dp[j] = max(dp[j], dp[j-w[i]] + v[i]) void solve() { for (int i = 1; i <= N; i++) { // 完全背包 /*for (int j = w[i]; j <= W; j++) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); }*/ // 01背包 /*for (int j = W; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); }*/ } printf("ans = %d", dp[W]); } int main() { cin >> N >> W; for(int i = 1; i <= N; i++){ cin >> w[i] >> v[i]; } memset(dp, 0, sizeof dp); solve(); return 0; }01背包之2
当w的范围很大的时候，不能通过计算重量范围内价值的最大值。 此时可以反过来，求价值范围内重量的最小值。
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<limits.h> #include<algorithm> using namespace std; typedef long long ll; // 物品总数上限 const int MAX_N = 100; const int MAX_V = 100; const int INF = INT_MAX; // 物品总数 int N; // 重量上限 int W; // 每个物品的重量和价格 int w[MAX_N], v[MAX_N]; // dp数组 ll dp[MAX_N + 1][MAX_N * MAX_V + 1]; // 状态转移方程 // dp[i][j] = min(dp[i-1][j], dp[i-1][j - v[i]] + w[i]); void solve() { fill(dp[0], dp[0] + (MAX_N*(MAX_N * MAX_V + 1)), INF); dp[0][0] = 0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= MAX_N * MAX_V; j++) { if (j < v[i]) dp[i][j] = dp[i-1][j]; else dp[i][j] = min(dp[i-1][j], dp[i-1][j - v[i]] + w[i]); } } int res = 0; for (int i = 0; i <= MAX_N * MAX_V; i++) { if (dp[N][i] <= W) res = i; // 没有break } printf("res = %d", res); } int main() { cin >> N >> W; for(int i = 1; i <= N; i++){ cin >> w[i] >> v[i]; } solve(); return 0; }注意！int型的数组存INT_MAX会爆炸！！！
fill()函数 fill函数可以赋值任何，使用方法特别简便：
例如int数组：fill(arr, arr + n, 要填入的内容);vector也可以：fill(v.begin(), v.end(), 要填入的内容);二维数组dp[ i ][ j ]：fill(dp[0], dp[0] + (MAX_N*(MAX_N * MAX_V + 1)), INF);多重部分求和问题
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<limits.h> #include<algorithm> using namespace std; typedef long long ll; // 上限 const int MAX_N = 100; const int MAX_K = 100000; // 数字总数 int n; // 目标K值 int K; // 数字和个数 int a[MAX_N], m[MAX_N]; // 改良方案： // dp数组 int dp[MAX_K + 10]; // 状态转移方程 // 1. dp[j] >= 0 // -->> dp[j] = m[i] // 2. j < a[i] || dp[j - a[i]] <= 0 // -->> dp[j] = -1 // 3. // -->> dp[j] = dp[j - a[i]] - 1 void solve() { memset(dp, -1, sizeof dp); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= K; j++) { if (dp[j] >= 0) { dp[j] = m[i]; } else if (j < a[i] || dp[j - a[i]] <= 0) { dp[j] = -1; } else { dp[j] = dp[j - a[i]]-1; } } for (int p = 0; p <= K; p++) { printf("%3d", dp[p]); } cout << endl; } if (dp[K] >= 0) printf("Yes\n"); else printf("No\n"); } // 一般方案: // dp数组 /*bool dp[MAX_N + 10][MAX_K + 10]; // 状态转移方程 // dp[i+1][j] |= dp[i][j-k*a[i]] // void solve() { dp[0][0] = true; for (int i = 0; i < n; i++) { for (int j = 0; j <= K; j++) { for (int k = 0; k <= m[i] && k * a[i] <= j; k++) { dp[i + 1][j] |= dp[i][j - k * a[i]]; } } } if (dp[n][K]) printf("Yes\n"); else printf("No\n"); }*/ int main() { cin >> n >> K; for(int i = 0; i < n; i++){ cin >> a[i] >> m[i]; } solve(); return 0; }最长上升子序列
解法一：
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<limits.h> #include<algorithm> using namespace std; typedef long long ll; // 上限 const int MAX_N = 1000; // 数字总数 int n; // 数字和个数 int a[MAX_N]; // dp数组 int dp[MAX_N + 10]; void solve() { int res = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1); } res = max(res, dp[i]); } cout << "res = " << res << endl; } int main() { cin >> n; for(int i = 0; i < n; i++){ cin >> a[i]; } fill(dp, dp + MAX_N + 10,1); solve(); return 0; }解法二： lower_bound(arr, arr+arr.length, des) 这个函数是从已经排好序的序列a中利用二分搜索找出指向满足arr[i] >= des的arr的最小的指针。 比如：0 2 6 7 8 9 100 100 100 现在执行lower_bound(arr, arr+length, 10)，找到的就是第一个大于等于10的数的位置，即100。
扩展： 还有一个upper_bound(arr, arr+arr.length, des)它是找出指向满足arr[i] > des的arr的最小的指针。
可以通过upper_bound(a, a+n, k) - lower_bound(a, a+n, k)求出数组a中k的个数。
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<limits.h> #include<algorithm> using namespace std; typedef long long ll; // 上限 const int MAX_N = 1000; const int INF = 1 << 31 - 1; // 数字总数 int n; // 数字和个数 int a[MAX_N]; // dp数组 int dp[MAX_N + 10]; void solve() { fill(dp, dp + n, INF); for (int i = 0; i < n; i++) { *lower_bound(dp, dp + n, a[i]) = a[i]; for (int j = 0; j < n; j++) { printf("%4d", dp[j]); } cout << endl; } printf("res = %d\n", lower_bound(dp, dp + n, INF) - dp); } int main() { cin >> n; for(int i = 0; i < n; i++){ cin >> a[i]; } solve(); return 0; }测试数据：
输入：
12 1 11 9 8 7 2 3 4 5 8 6 9输出：
1 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 11 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 9 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 8 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 7 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 2 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 2 3 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 2 3 4 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 2 3 4 5 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 2 3 4 5 8 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 2 3 4 5 6 1073741824 1073741824 1073741824 1073741824 1073741824 1073741824 1 2 3 4 5 6 9 1073741824 1073741824 1073741824 1073741824 1073741824 res = 7划分数
求n的m划分，结果 % M。
dp[i][j]：j的i划分 状态转移方程：dp[i][j] = dp[i][j - i] + dp[i - 1][j]
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<limits.h> #include<algorithm> using namespace std; typedef long long ll; // 上限 const int MAX_N = 1000; const int INF = 1 << 31 - 1; // 数字总数 int n, m, M; // dp数组 int dp[MAX_N + 10][MAX_N + 10]; void solve() { dp[0][0] = 1; for (int i = 1; i <= m; i++) { for (int j = 0; j <= n; j++) { if (j >= i) { dp[i][j] = (dp[i][j - i] + dp[i - 1][j]) % M; } else { dp[i][j] = dp[i - 1][j]; } } } printf("ans = %d\n", dp[m][n]); } int main() { cin >> n >> m >> M; solve(); return 0; }多重集组合数
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<limits.h> #include<algorithm> using namespace std; typedef long long ll; // 上限 const int MAX_N = 1000; const int INF = 1 << 31 - 1; // 数字总数，取的数字数 int n, m, M; // 数字个数 int a[MAX_N]; // dp数组 int dp[MAX_N + 10][MAX_N + 10]; // dp[i][j]: 从前i个数选j个组合总数 // 状态转移方程: // j-1 >= ai // dp[i + 1][j] = dp[i][j] + dp[i + 1][j - 1] - dp[i][j - 1 - a[i]] // else // dp[i + 1][j] = dp[i][j] + dp[i + 1][j - 1] void solve() { for (int i = 0; i <= n; i++) { dp[i][0] = 1; } for (int i = 0; i < n; i++) { for (int j = 1; j <= m; j++) { // 解法一： /*int k = min(j, a[i]); while(k >= 0) { dp[i + 1][j] += dp[i][j - k]; k--; }*/ // 解法二：实际上是解法一的变形 if (j - 1 >= a[i]) { dp[i + 1][j] = dp[i][j] + dp[i + 1][j - 1] - dp[i][j - 1 - a[i]]; } else { dp[i + 1][j] = dp[i][j] + dp[i + 1][j - 1]; } } } printf("ans = %d\n", dp[n][m]); } int main() { cin >> n >> m >> M; for (int i = 0; i < n; i++) { cin >> a[i]; } solve(); return 0; }小顶堆
小顶堆可以这样直接定义 priority_queue<int, vector<int>, greater<int> > que; #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<queue> #include<limits.h> #include<algorithm> using namespace std; typedef long long ll; int heap[MAX_N], sz = 0; void push(int x) { int i = sz++; while (i > 0) { int p = (i - 1) / 2; if (heap[p] <= x) break; heap[i] = heap[p]; i = p; } heap[i] = x; } int pop() { int ret = heap[0]; // 最小值 int i = 0; // 从根开始向下替换 int x = heap[--sz]; // 要提到根的数值 while (i * 2 + 1 < sz) { int a = i * 2 + 1; int b = i * 2 + 2; if (heap[a] > heap[b]) swap(a,b); if (heap[a] > x) break; heap[i] = heap[a]; i = a; } heap[i] = x; return ret; } int main() { int k = 5; push(2); push(3); push(5); push(1); push(0); while (k--) { cout << pop() << endl; } }注意：
大顶堆可以直接使用priority_queue<int> que（默认为大顶堆）实现。 小顶堆可以通过定义成 priority_queue<int, vector<int>, greater<int>> que来实现。set和map的用法：
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<queue> #include<set> #include<map> #include<limits.h> #include<algorithm> using namespace std; typedef long long ll; // 上限 const int MAX_N = 1000; const int INF = 1 << 31 - 1; int main() { map<int, int> mp; mp[1]++; mp[3]++; mp[1]++; mp[2]++; mp[4]++; mp[2]++; map<int, int>::iterator iter; for (iter = mp.begin(); iter != mp.end(); iter++) { cout << "key : " << iter->first << ", value :" << iter->second << endl; } mp.erase(2); cout << endl; for (iter = mp.begin(); iter != mp.end(); iter++) { cout << "key : " << iter->first << ", value :" << iter->second << endl; } cout << "--------------------" << endl; set<int> st; st.insert(10); st.insert(1); st.insert(3); st.insert(5); if (st.find(5) != st.end()) cout << "Found:" << 5 << endl; else cout << "Not found:" << 5 << endl; for (set<int>::iterator it = st.begin(); it != st.end(); it++) { cout << *it << endl; } st.erase(5); cout << endl; for (set<int>::iterator it = st.begin(); it != st.end(); it++) { cout << *it << endl; } return 0; }并查集
int n; int par[MAX_N]; int rank[MAX_N]; void init(int n) { for (int i = 0; i < n; i++) { par[i] = i; rank[i] = 0; } } int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x != y) { if (rank[x] < rank[y]) par[x] = y; else if (rank[x] > rank[y]) par[y] = x; else{ par[y] = x; rank[x]++; } } } bool same(int x, int y) { return find(x) == find(y); }图
邻接表实现
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<algorithm> typedef long long ll; using namespace std; const int MAX_N = 1000; int n; vector<int> G[100]; struct edge{ int to, cost; }; vector<edge> v[100]; int main() { int n; cin >> n; // 使用G /*for (int i = 0; i < n; i++) { int s, t; scanf("%d %d", &s, &t); G[s].push_back(t); } for (vector<int>::iterator iter = G[1].begin(); iter != G[1].end(); iter++) { cout << *iter << endl; }*/ // 使用v for (int i = 0; i < n; i++) { int s, t; scanf("%d %d", &s, &t); edge et; et.to = t; et.cost = 10; v[s].push_back(et); } for (int i = 0; i < v[1].size(); i++) { edge e = v[1][i]; cout << "e : " << e.to << " ->> " << e.cost << endl; } return 0; }二分图
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<iomanip> #include<algorithm> typedef long long ll; using namespace std; const int MAX_N = 1000; int n, v; vector<int> G[MAX_N+10]; int color[MAX_N+10]; // struct edge{ int to, cost; }; // vector<edge> v[100]; bool dfs(int s, int c) { color[s] = c; for (int i = 0; i < G[s].size(); i++) { if (color[G[s][i]] == c) return false; if (color[G[s][i]] == 0 && !dfs(G[s][i], -c)) return false; } return true; } void solve() { for (int i = 0; i < n; i++) { if (color[i] == 0) { if (!dfs(i, 1)) { cout << "NO" << endl; return ; } } } cout << "Yes" << endl; } int main() { cin >> n >> v; for (int i = 0; i < v; i++) { int s, t; cin >> s >> t; G[s].push_back(t); G[t].push_back(s); } solve(); return 0; }图的单源最短路问题（Dijkstra）
Dijkstra： 1.找到最短距离已经确定的点，从它出发更新x相邻顶点的最短距离 2.此后不需要再关心1中的“最短距离已经确定的顶点”
简单的来说就是：从源头顶点开始，不断找离源头顶点最近的点向外扩枝（最开始是从源头开始，因为离源头最近的是它自己），使用过的点不再使用，最终得到源头到各个点的最短距离，到达不了为INF。
注意：在图中存在负边，Dijkstra算法无法正确求解问题。
const int MAX_V = 1000; const int INF = 1 << 31 - 1; // cost[i][j]表示从i到j的权值，没有为0 int d[MAX_V]; // d[i]表示源头节点到i节点的最短距离 int cost[MAX_V][MAX_V]; // 表示节点是否被使用过 bool used[MAX_V]; // 边的总数 int V; // s为源头节点 // 输入数据：s d q ----> cost[s][d] = q; void dijkstra(int s) { fill(d, d+MAX_V, INF); d[s] = 0; fill(used, used+MAX_V, false); while (true) { int v = -1; for (int i = 0; i < V; i++) { if (!used[i] && (v == -1 || d[i] < d[v])) v = i; } if (v == -1) break; //都使用过 used[v] = true; for (int i = 0; i < V; i++) { d[i] = min(d[i], d[v] + cost[v][i]); } } }使用优先队列（最小堆）实现Dijkstra算法
// 边信息结构体 struct edge { int to, cost; }; // 邻接表存储边信息 vector<edge> G[MAX_V]; // 存储 顶点当前最短距离和顶点编号 typedef pair<int, int> P; // cost[i][j]表示从i到j的权值，没有为0 int d[MAX_V]; // s为源头顶点 void dijkstra(int s) { priority_queue que<P, vector<P>, greater<P>> que; fill(d, d+MAX_N, INF); d[s] = 0; que.push(P(0, s)); while(!que.empty()) { // 取路径最短的顶点 P p = que.top(); que.pop(); // 得到它的顶点编号 int v = p.second; // 如果已经使用过 if (d[v] < p.first) continue; // 找与它相关的顶点, 如果从这个顶点点到他相通的顶点距离更短则设置距离并加入队列 // 就是不断找未使用过的并且与根节点距离最短的节点，然后向外扩枝，重复这个操作直到所有顶点都被使用 for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; if (d[v] + e.cost < d[e.to]) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } }实现：
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<iomanip> #include<algorithm> typedef long long ll; using namespace std; const int MAX_V = 1000; const int INF = 1 << 31 - 1; int n, v; struct edge { int to, cost; }; vector<edge> G[MAX_V]; int d[MAX_V]; typedef pair<int, int> P; void dijkstra(int s) { fill(d, d+v, INF); d[s] = 0; priority_queue<P, vector<P>, greater<P>> que; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first) continue; for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; cout << "d[" << e.to << "] = " << d[e.to] << endl; que.push(P(d[e.to], e.to)); } } } } void solve(int s) { dijkstra(s); } /* 测试样例: 5 6 0 1 1 2 1 1 3 0 1 1 3 1 3 2 1 4 3 1 */ int main() { cin >> n >> v; for (int i = 0; i < v; i++) { int s, t, c; cin >> s >> t >> c; edge e; e.to = t; e.cost = c; G[s].push_back(e); } solve(4); for (int i = 0; i < n; i++) { cout << d[i] << " "; } return 0; }Floyd-Warshall算法
实际就是动态规划，复杂度为O(n^3) 状态转移方程：d[i][j] = d[i][k] + d[k][i]
需要注意先将d[ ][ ]初始化为INF，然后再输入值，并且d[ i ][ i ] = 0。
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<iomanip> #include<algorithm> typedef long long ll; using namespace std; const int MAX_V = 1000; const int INF = (1 << 31) - 1; int n, v; int d[MAX_V][MAX_V]; void warshall_floyd() { for (int i = 0; i < n; i++) { d[i][i] = 0; } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (d[i][k] != INF && d[k][j] != INF) d[i][j] = min(d[i][j], d[i][k]+d[k][j]); } } } } void solve() { warshall_floyd(); } /* 测试样例: 5 6 0 1 1 2 1 1 3 0 1 1 3 1 3 2 1 4 3 1 */ int main() { fill (d[0], d[0]+MAX_V*MAX_V, INF); cin >> n >> v; for (int i = 0; i < v; i++) { int s, t, c; cin >> s >> t >> c; d[s][t] = c; } // 初始状态： cout << "初始状态: " << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf("%13d", d[i][j]); } cout << endl; } cout << endl << endl; solve(); // 结果 cout << "结果: " << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf("%13d", d[i][j]); } cout << endl; } return 0; }可以得到路径的Dijkstra，增加函数getPath()
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<iomanip> #include<algorithm> typedef long long ll; using namespace std; const int MAX_V = 1000; const int INF = 1 << 31 - 1; int n, v; struct edge { int to, cost; }; vector<edge> G[MAX_V]; int d[MAX_V], pre[MAX_V]; typedef pair<int, int> P; void dijkstra(int s) { fill(pre, pre+MAX_V, -1); fill(d, d+v, INF); d[s] = 0; priority_queue<P, vector<P>, greater<P>> que; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first) continue; for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; pre[e.to] = v; cout << "d[" << e.to << "] = " << d[e.to] << endl; que.push(P(d[e.to], e.to)); } } } } void getPath(int t) { vector<int> path; for ( ; t != -1; t = pre[t]) path.push_back(t); reverse(path.begin(), path.end()); for (int i = 0; i < path.size(); i++) { cout << path[i] << " "; } } void solve(int s) { dijkstra(s); } /* 测试样例: 5 6 0 1 1 2 1 1 3 0 1 1 3 1 3 2 1 4 3 1 */ int main() { cin >> n >> v; for (int i = 0; i < v; i++) { int s, t, c; cin >> s >> t >> c; edge e; e.to = t; e.cost = c; G[s].push_back(e); } solve(4); for (int i = 0; i < n; i++) { cout << d[i] << " "; } cout << endl << endl << "Path:" << endl; getPath(1); return 0; }Prim算法
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<iomanip> #include<algorithm> typedef long long ll; using namespace std; const int MAX_V = 1000; const int INF = 1 << 31 - 1; int n, v; // 边的权值，不存在为INF int cost[MAX_V][MAX_V]; // 到各个顶点的最短路径 int mincost[MAX_V]; // 是否加入生成树 bool used[MAX_V]; // 以4为初始节点 // Prim算法默是当前图为连通图 int prim() { fill(used, used+MAX_V, false); fill(mincost, mincost+MAX_V, INF); mincost[4] = 0; // 表示从哪个节点开始生成 最小生成树 int res = 0; while (true) { int v = -1; // 找出离当前集合距离最短的顶点 for (int i = 0; i < n; i++) { if (!used[i] && (v == -1 || mincost[i] < mincost[v])) v = i; } // 所有点在集合中，退出 if (v == -1) break; used[v] = true; res += mincost[v]; // 加入最小生成树 // 从 离当前集合距离最短的顶点 向外扩枝 for (int i = 0; i < n; i++) { mincost[i] = min(mincost[i], mincost[v] + cost[v][i]); } } return res; } void solve() { cout << "最小生成树为: " << prim(); } /* 测试样例: 5 6 0 1 1 2 1 1 3 0 1 1 3 1 3 2 1 4 3 1 */ int main() { fill(cost[0], cost[0]+MAX_V*MAX_V, INF); cin >> n >> v; for (int i = 0; i < v; i++) { int s, t, c; cin >> s >> t >> c; cost[s][t] = c; } solve(); cout << endl; for (int i = 0; i < n; i++) { cout << mincost[i] << " "; } return 0; }优先队列实现Prim算法
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<iomanip> #include<algorithm> typedef long long ll; using namespace std; const int MAX_V = 1000; const int INF = 1 << 31 - 1; int n, v; typedef pair<int, int> P; // 边的数据结构 struct edge { int to, cost; }; // 边 vector<edge> cost[MAX_V]; // 到各个顶点的最短路径 int mincost[MAX_V]; // 以4为初始节点 // Prim算法默是当前图为连通图 int prim() { fill(mincost, mincost+MAX_V, INF); mincost[4] = 0; // 表示从哪个节点开始生成 最小生成树 int res = 0; priority_queue<P, vector<P>, greater<P>> que; que.push(P(0 ,4)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (mincost[v] < p.first) continue; res += p.first; for (int i = 0; i < cost[v].size(); i++) { edge e = cost[v][i]; if (mincost[e.to] > mincost[v] + e.cost) { mincost[e.to] = mincost[v] + e.cost; que.push(P(mincost[e.to], e.to)); } } } return res; } void solve() { cout << "最小生成树为: " << prim(); } /* 测试样例: 5 6 0 1 1 2 1 1 3 0 1 1 3 1 3 2 1 4 3 1 */ int main() { cin >> n >> v; for (int i = 0; i < v; i++) { int s, t, c; cin >> s >> t >> c; edge e; e.to = t; e.cost = c; cost[s].push_back(e); } solve(); cout << endl; for (int i = 0; i < n; i++) { cout << mincost[i] << " "; } return 0; }使用并查集实现Kruskal算法
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<iomanip> #include<algorithm> typedef long long ll; using namespace std; const int MAX_V = 1000; const int INF = 1 << 31 - 1; int n, v; // 边数据结构 struct edge { int s, t, cost; }; // 边的集合 edge es[MAX_V]; int p[MAX_V]; int r[MAX_V]; void init_union_find(int num) { for (int i = 0; i < num; i++) { p[i] = i; r[i] = 0; } } int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); } void unite(int a, int b) { a = find(a); b = find(b); if (a != b) { if (r[a] < r[b]) { p[a] = b; } else if(r[a] > r[b]) { p[b] = a; } else { p[b] = a; r[a]++; } } } bool same(int a, int b) { return find(a) == find(b); } bool comp(const edge& e1, const edge& e2) { return e1.cost < e2.cost; } // 以4为初始节点 int kruskal() { sort(es, es+v, comp); init_union_find(n); int res = 0; for (int i = 0; i < n; i++) { edge e = es[i]; if (!same(e.s, e.t)) { unite(e.s, e.t); res += e.cost; cout << e.s << " " << e.t << endl; cout << "res = " << res << endl; } } return res; } void solve() { cout << "最小生成树为: " << kruskal(); } /* 测试样例: 5 6 0 1 1 2 1 1 3 0 1 1 3 1 3 2 1 4 3 1 */ int main() { cin >> n >> v; for (int i = 0; i < v; i++) { int s1, t1, c; cin >> s1 >> t1 >> c; edge e; e.s = s1; e.t = t1; e.cost = c; es[i] = e; } solve(); return 0; }尺取法
#include<cstdio> #include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #include<map> using namespace std; int n, S; int a[10000]; void solve() { int res = n+1; int s = 0, t = 0, sum = 0; while (1) { while (t < n && sum < S) { sum += a[t++]; } if (sum < S) break; res = min(res, t-s); sum -= a[s++]; } if (res > n) { res = 0; } cout << res << endl; } int main() { cin >> n >> S; for (int i = 0; i < n; i++) { cin >> a[i]; } solve(); return 0; }