第一部分 动态规划
最大连续子数字和
1
2
3
4
5
6
7
8
| int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
|
01背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <iostream>
#define MAX 1001
using namespace std;
int dp[MAX];
int main() {
int w[MAX], v[MAX], n, wei;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &w[i], &v[i]);
}
scanf("%d", &wei);
// Dynamic Programming START
for (int i = 1; i <= n; i++) {
for (int j = wei; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
// END
printf("%d\n", dp[wei]);
return 0;
}
/*
运行时间：O(n*wei)
Example:
Input:
4
2 3
1 2
3 4
2 2
5
Output:
7
Program ended with exit code: 0
*/
|
完全背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#define MAX 1001
using namespace std;
int dp[MAX];
int main() {
int w[MAX], v[MAX], n, wei;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &w[i], &v[i]);
}
scanf("%d", &wei);
// Dynamic Programming START
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= wei; j++) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
// END
printf("%d\n", dp[wei]);
return 0;
}
/*
运行时间：O(n*wei)
Example:
Input:
4
2 3
1 2
3 4
2 2
5
Output:
10
Program ended with exit code: 0
*/
|
图论
dijkstra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <queue>
using namespace std;
const int N = 500;
const int INF = 99999999;
int vis[N];
int dis[N];
int iMap[N][N];
int vertexs;
int edges;//这里有个玄学问题，如果edges 放在vis[N],之前的话程序无法运行。。
int u, v, w;
int dijkstraHeap(int beginX, int endX)
{
int minVertex;
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > heap;//一个最小堆
//初始化
for(int i=1;i<=vertexs;i++){
dis[i] = iMap[beginX][i];//初始化所有点到开始点的最短距离
heap.push(make_pair(dis[i], i));//初始的话先将所有的点入队
vis[i] = 0;
}
vis[beginX] = 1;
while(!heap.empty()){
minVertex = heap.top().second;
heap.pop();
if(vis[minVertex]) continue;//如果这个点之前没有被访问过
vis[minVertex] = 1;
int u = minVertex;
for(int v=1;v<=vertexs;v++){
if(!vis[v] && iMap[u][v] < INF){//如果这个点未被访问，且中间有路径到达
if(dis[v] > iMap[u][v] + dis[u]){
dis[v] = iMap[u][v] + dis[u];
heap.push(make_pair(dis[v], v));//将到更新后的到该点的距离入队
}
}
}
}
return dis[endX];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <iostream>
#define MAX 1001
using namespace std;
int main() {
int inf = MAX, nodeCount, lineCount, x, y, s, point, u = 0, minimum;
int map[MAX][MAX], dis[MAX];
bool book[MAX];
for (int i = 0; i < MAX; i++) {
book[i] = false;
for (int j = 0; j < MAX; j++) {
if (i == j) map[i][j] = 0;
else map[i][j] = inf;
}
}
scanf("%d%d", &nodeCount, &lineCount);
for (int i = 0; i < lineCount; i++) {
scanf("%d%d%d", &x, &y, &s);
map[x][y] = s;
}
scanf("%d", &point);
// Dijkstra START
for (int i = 0; i < nodeCount; i++) {
dis[i] = map[point][i];
}
book[point] = true;
for (int i = 0; i < nodeCount; i++) {
minimum = inf;
for (int j = 0; j < nodeCount; j++) {
if (!book[j] && dis[j] < minimum) {
minimum = dis[j];
u = j;
}
}
book[u] = true;
for (int j = 0; j < nodeCount; j++)
if (map[u][j] < inf)
dis[j] = min(dis[j], dis[u] + map[u][j]);
}
// END
for (int i = 0; i < nodeCount; i++) {
printf("%d -> %d: ", point, i);
if (dis[i] >= inf) printf("can not reach\n");
else printf("%d\n", dis[i]);
}
return 0;
}
/*
求单源最短路径
运行时间：O(n^2) // 用堆和邻接表优化可以降至 O(m+N)logN
Example:
Input:
3 4
0 1 1
1 2 2
2 0 3
0 2 2
1
Output:
1 -> 0: 5
1 -> 1: 0
1 -> 2: 2
Program ended with exit code: 0
*/
|
度序列可简单验证 Erdős–Gallai
$S=(d_1,d_2,…,d_n)$为多个非负整数组成的非递增序列 S可简单图化当且仅当这些数字的和为偶数，且 $\sum^k_{i=1}d_i\leqslant k(k-1)+ \sum^k_{i=k+1} min(d_i,k)$ $1 \leqslant k \leqslant n$对于任意都成立。 对前k个点分配度数，除了两两能连k(k-1)/2 边外，剩下的度数由后面点的度数补充。 因为di非递增，从小到大枚举k，维护di后缀与k取min的和
d是终点，counter是入度统计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| int d[MAXN], counter[MAXN];
int n;
bool erdos_gallai() {
memset(counter, 0, sizeof(counter));
for (int i = 0; i < n; i++) counter[d[i]]++;
int remaining = 0, i = 0, cur;
ll left = 0, right = 0;
for (int k = 0; k < n; k++) {
cur = d[i++];
left += cur;
counter[cur]--;
remaining += counter[k];
right += n - k - remaining - min(cur, k);
if (left > (ll)k * (k + 1) + right) {
return false;
}
}
return true;
}
|
Floyd-Warshall 多源最小路程
1
2
3
4
5
| for (int k = 0; k < nodeCount; k++)
for (int i = 0; i < nodeCount; i++)
for (int j = 0; j < nodeCount; j++)
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
|
KM 最优图匹配
完备匹配：定义 设G＝为二部图，|V1|≤|V2|，M为G中一个最大匹配，且|M|＝|V1|，则称M为V1到V2的完备匹配。也就是说把一个集合中的点全部匹配到另一个集合中。 二分图带权匹配与最优匹配：什么是二分图的带权匹配？二分图的带权匹配就是求出一个匹配集合，使得集合中边的权值之和最大或最小，这个匹配集合比一定是完备匹配。 对二分图G和一组可行标, 满足可行标边界条件(lx[i]+ly[j]=w[i,j])的所有边构成的生成子图(需要包含所有顶点), 称为其等价子图(相等子图), 在这个等价子图上,寻找其完备匹配,如果完备匹配存在,则这个完备匹配M就是图G的最大权匹配, 最大权等于所有可行标的和; 如果完备匹配不存在,则修改可行标,用贪心的思想,将最优的边加入等价子图. Kuhn－Munkras算法流程： (1)初始化可行顶标的值 (2)用匈牙利算法寻找完备匹配 (3)若未找到完备匹配则修改可行顶标的值 (4)重复(2)(3)直到找到相等子图的完备匹配为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| /******************************************************
二分图最佳匹配 （kuhn munkras 算法 O(m*m*n)).
邻接矩阵形式 。 返回最佳匹配值，传入二分图大小m,n
邻接矩阵 mat ，表示权，match1,match2返回一个最佳匹配,为匹配顶点的match值为-1，
一定注意m<=n，否则循环无法终止，最小权匹配可将全职取相反数。
初始化： for(i=0;i<MAXN;i++)
for(j=0;j<MAXN;j++) mat[i][j]=-inf;
对于存在的边：mat[i][j]=val;//注意不能负值
********************************************************/
#include<string.h>
#define MAXN 310
#define inf 1000000000
#define _clr(x) memset(x,-1,sizeof(int)*MAXN)
int KM(int m,int n,int mat[][MAXN],int *match1,int *match2)
{
int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN];
int p,q,i,j,k,ret=0;
for(i=0;i<m;i++)
{
l1[i]=-inf;
for(j=0;j<n;j++)
l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
if(l1[i]==-inf) return -1;
}
for(i=0;i<n;i++)
l2[i]=0;
_clr(match1);
_clr(match2);
for(i=0;i<m;i++)
{
_clr(t);
p=0;q=0;
for(s[0]=i;p<=q&&match1[i]<0;p++)
{
for(k=s[p],j=0;j<n&&match1[i]<0;j++)
{
if(l1[k]+l2[j]==mat[k][j]&&t[j]<0)
{
s[++q]=match2[j];
t[j]=k;
if(s[q]<0)
{
for(p=j;p>=0;j=p)
{
match2[j]=k=t[j];
p=match1[k];
match1[k]=j;
}
}
}
}
}
if(match1[i]<0)
{
i--;
p=inf;
for(k=0;k<=q;k++)
{
for(j=0;j<n;j++)
{
if(t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
p=l1[s[k]]+l2[j]-mat[s[k]][j];
}
}
for(j=0;j<n;j++)
l2[j]+=t[j]<0?0:p;
for(k=0;k<=q;k++)
l1[s[k]]-=p;
}
}
for(i=0;i<m;i++)
ret+=mat[i][match1[i]];
return ret;
}
|
