算法

染色问题 同染色（连接点染相同颜色） 用法 得到各个连通分量（分组）。 代码 #include<bits/stdc++.h> using namespace std; const int MAXN = 100; int graph[MAXN][MAXN]; int color[MAXN]; int cnt; //连通分量数量 void dfs(int index,int n,int c) { color[index]=c; for(int i=0;i<n;i++) if(graph[index][i]&&!color[i]) dfs(i,n,c); } int main() { int n,m; cin >> n >> m; for(int i=0;i<m;i++) { int s,t; cin >> s >> t; graph[s][t]=1,graph[t][s]=1; } for(int i=0;i<n;i++) { if(!color[i]) { cnt++; dfs(i,n,cnt); } } vector<vector<int>> group(cnt+1,vector<int>()); for(int i=0;i<n;i++) group[color[i]].push_back(i); for(int i=1;i<=cnt;i++) { cout << "颜色" << i << ":"; for(int j=0;j<group[i].size();j++) cout << group[i][j] << ' '; cout << endl; } } 异染色（连接点染不同颜色） 用法 得到二分图。 代码 #include<bits/stdc++.h> using namespace std; const int MAXN = 100; //假如最大100个结点的图 int graph[MAXN][MAXN]; int color[MAXN]; //用于确定分组,颜色为1和2 int dfs(int index,int n,int c) //仅仅用来染色出发点所在的连通分量 { //直接用对边不同色考虑 color[index]=c; for(int i=0;i<n;i++) if(graph[index][i] && (color[i]==c || (color[i]==0 && !dfs(i,n,3-c))) ) return 0; return 1; } int main() { int n,m; cin >> n >> m; for(int i=0;i<m;i++) { int s,t; cin >> s >> t; graph[s][t]=1,graph[t][s]=1; } for(int i=0;i<n;i++) { if(!color[i]) if(!dfs(i,n,1)) { cout << "错误，不是二分图" << endl; return 0; } } vector<int> color1,color2; for(int i=0;i<n;i++) { if(color[i]==1) color1.push_back(i); if(color[i]==2) color2.push_back(i); } cout << "染色结果:" << endl; for(int i=0;i<color1.size();i++) cout << color1[i] << ' '; cout << endl; for(int i=0;i<color2.size();i++) cout << color2[i] << ' '; return 0; } 注 这两个染色问题都可以用邻接矩阵做。我用int-MAXN是因为简单:)。

P1177 【模板】排序 - 洛谷 我用归并排序写的。(时间复杂度O(nlogn),空间复杂度O(n))。 #include<bits/stdc++.h> using namespace std; vector<int> A; //归并排序 void gbsort(int l,int r) { vector<int> temp; if(l==r) return; int m=((l+r)>>1); printf("划分的区间:[%d,%d],[%d,%d]\n",l,m,m+1,r); gbsort(l,m); gbsort(m+1,r); int curL=l,curR=m+1; //左右分为[l,m] [m+1,r] for(int i=0;i<r-l+1;i++) { if( curL>m ) { temp.push_back(A[curR]); curR++; } else if( curR>r ) { temp.push_back(A[curL]); curL++; } else if(A[curL]>A[curR]) { temp.push_back(A[curR]); curR++; } else if(A[curL]<=A[curR]) { temp.push_back(A[curL]); curL++; } } for(int i=l;i<=r;i++) { A[i]=temp[i-l]; } } int main() { int N; cin >> N; for(int i=0;i<N;i++) { int x; cin >> x; A.push_back(x); } // sort(A.begin(),A.end()); gbsort(0,N-1); for(int i=0;i<N;i++) { cout << A[i] << ' '; } return 0; } C++标准库sort用的是快速排序

不详解，看例题就完了。

前提算法 二分图染色得到L，R数组 （以下是利用染色得到二分图的代码） #include<bits/stdc++.h> using namespace std; const int MAXN = 100; //假如最大100个结点的图 int graph[MAXN][MAXN]; int color[MAXN]; //用于确定分组,颜色为1和2 int dfs(int index,int n,int c) //仅仅用来染色出发点所在的连通分量 { //直接用对边不同色考虑 color[index]=c; for(int i=0;i<n;i++) if(graph[index][i] && (color[i]==c || (color[i]==0 && !dfs(i,n,3-c))) ) return 0; return 1; } int main() { int n,m; cin >> n >> m; for(int i=0;i<m;i++) { int s,t; cin >> s >> t; graph[s][t]=1,graph[t][s]=1; } for(int i=0;i<n;i++) { if(!color[i]) if(!dfs(i,n,1)) { cout << "错误，不是二分图" << endl; return 0; } } vector<int> color1,color2; for(int i=0;i<n;i++) { if(color[i]==1) color1.push_back(i); if(color[i]==2) color2.push_back(i); } cout << "染色结果:" << endl; for(int i=0;i<color1.size();i++) cout << color1[i] << ' '; cout << endl; for(int i=0;i<color2.size();i++) cout << color2[i] << ' '; return 0; } 染色后，可以用来得到最大匹配，最大匹配又可以用来得到最小点覆盖，最小点覆盖又可以用来实现匈牙利算法，匈牙利算法用可以用来解决指派问题。顺了，都理顺了:)。 最大匹配 面向问题 求解一个二分图中的最大匹配问题。 总体思路 从任意一个顶点出发， 写代码 1. 起步：初始化所用变量与内存。 const int MAXN : 根据题目调整 int n : 两边的顶点总数 int graph[MAXN][MAXN] : 基于二维数组的邻接矩阵 int match[MAXN] : match[i]表示与i匹配的点(因为最大匹配饱和点中每一个点都只可能与唯一点匹配)，如果为-1表示未匹配 int used[MAXN] : dfs访问标记（这个级别低于匹配标记match） 2. 深入： 了解所用函数。 ...

01背包 问题 有N个物品要装到一个只能承重W的背包里，每个物品重量为w[i]（weight），价值为v[i]（value），问背包能装的最大价值 前提 每类物品只能装一个（此谓01）。 二维解法 /*01背包二维数组解决*/ #include<bits/stdc++.h> using namespace std; int main() { int N,W; //物品种类数,背包总能承受重量 cin >> N >> W; int w[N+1]; //每个物品的重量,从1开始 int v[N+1]; //每个物品的价值,从1开始 int dp[N+1][W+1]; //dp[i][j]表示考虑第i个物品,总重量为j时,能达到的最大价值 for(int i=1;i<=N;i++) cin >> w[i] >> v[i]; //重量 价值 for(int i=0;i<=N;i++) for(int j=0;j<=W;j++) dp[i][j]=0; for(int i=1;i<=N;i++) for(int j=W;j>=w[i];j--) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); //(不用第i个物品,用第i个物品) cout << dp[N][W]; return 0; } 一维解法 int main() { int N,W; //物品种类数,背包总能承受重量 cin >> N >> W; int w[N+1]; //每个物品的重量,从1开始 int v[N+1]; //每个物品的价值,从1开始 int dp[W+1]; //dp[i][j]表示考虑第i个物品,总重量为j时,能达到的最大价值 for(int i=1;i<=N;i++) cin >> w[i] >> v[i]; //重量 价值 for(int i=0;i<=W;i++) dp[i]=0; for(int i=1;i<=N;i++) for(int j=W;j>=w[i];j--) dp[j] = max(dp[j],dp[j-w[i]]+v[i]); //(不用第i个物品,用第i个物品) cout << dp[W]; return 0; } 示例 输入 10 15 2 3 3 4 4 8 5 8 9 10 3 5 4 6 2 4 6 7 7 9 输出 26 完全背包 关于我 关于我

感觉KMP很简单就没练过，用的时候太不熟练，写个博客熟悉熟悉。 其实主要就是两部分，一个是确定next数组，一个是利用next找子串，这两部分大致思路很简单，有点异曲同工。 具体细节代码中注释已经说的很清楚了，不再赘述。 #include<bits/stdc++.h> using namespace std; vector<int> getNext(const string &pattern) { int m = pattern.size(); // 既可以用来初始化也可以作为循环出口 vector<int> next(m); next.push_back(0); // 一个字符无法匹配默认为0 int i=1; // 后缀匹配到的字符位置（只增不减） int p=0; // 记录当前最大前缀(末)位置(其实也就是p=next[0]) while(i<m) { if(next[p] == next[i]) { p++; // 缀数增加，要推进主串，同时构建next next.push_back(p); i++; // 向后推进 } else // 后缀断连 { if(p == 0) // 没有回退空间（找不到更小前后缀）,保持缀数不变,继续推进 { i++; } else { p = next[p-1]; // 前后缀长度回退，循环继续 } } } return next; } int main() { string text;// 原串 string pattern;// 要找的目标字符串 cin >> text; cin >> pattern; int n=text.size(); int m=pattern.size(); if(n < m) return 0; //长度不符合标准 vector<int> next = getNext(text); // 这里只处理查找到第一个匹配串的位置，如果多个匹配点,重置变量(p),继续匹配不间断输出就行 int j=0; // pattern(副)串匹配到的位置 int i=0; // text(主)串匹配到的位置 while(j<m) { if(pattern[j] == text[i]) { j++; i++; } else { if(j==0) // 无法回退 { i++; // 向前推进 } else { j = next[j-1]; } } } // 这时i位于找到的子串所在位置后面一个 printf("第一个匹配的子串位置是[%d,%d]\n",i-m,i-1); // 输出所在区间 return 0; }