算法模板与题目整理

链表

链表反转

https://leetcode.cn/problems/reverse-linked-list/

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* reverseList(ListNode* head) {
    ListNode* cur = head;
    ListNode* prev = nullptr;
    while(cur != nullptr) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }

    return prev;
}

检查回文链表

先使用快慢指针找到回文串的右部分，然后翻转右部分，再将两个链表进行比对。 https://leetcode.cn/problems/palindrome-linked-list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isPalindrome(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* rp = reverseList(slow->next);
    ListNode* lp = head;
    while(lp != nullptr && rp != nullptr) {
        if(lp->val != rp->val) return false;
        lp = lp->next;
        rp = rp->next;
    }
    return true;
}

区间翻转链表

假设需要翻转[l, r]，那么我们记录start=l, end=r+1, startPrev=start-1。翻转之后，startPrev->next = reversedHead, start->next = end。由于翻转之后head可能会被改变，因此需要在head前添加一个dummy节点用于找到新链表的头。 https://leetcode.cn/problems/reverse-linked-list-ii/

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
ListNode* reverseList(ListNode* head, ListNode* end) {
    ListNode* cur = head;
    ListNode* prev = nullptr;
    while(cur != end) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode* dummy = new ListNode(-1, head);
    ListNode* startPrev = dummy;
    ListNode* start = dummy;
    ListNode* end = dummy;
    
    for(int i = 0; i < left; i++) {
        startPrev = start;
        start = start->next;
    }

    for(int i = 0; i < right; i++) {
        end = end->next;
    }
    end = end->next;

    startPrev->next = reverseList(start, end);
    start->next = end;
    
    return dummy->next;
}

两两交换链表中的节点

思路和链表的区间翻转是一样的，区间的大小为2，需要特殊考虑奇数点的情况。 https://leetcode.cn/problems/swap-nodes-in-pairs/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode* swapPairs(ListNode* head) {
    ListNode* dummy = new ListNode(-1, head);
    ListNode* startPrev = dummy;
    ListNode* start = head;
    ListNode* end = head;
    while(end != nullptr) {
        // 奇数个点
        if(end->next == nullptr) {
            break;
        }
        end = end->next->next;
        
        startPrev->next = reverseList(start, end);
        start->next = end;
        startPrev = start;
        start = end;
    }
    return dummy->next;
}

K个一组翻转链表

两两交换链表节点的一般情况，区间大小为k，需要考虑不足k个点的情况。 https://leetcode.cn/problems/reverse-nodes-in-k-group

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
ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* dummy = new ListNode(-1, head);
    ListNode* startPrev = dummy;
    ListNode* start = head;
    ListNode* end = head;

    while(end != nullptr) {
        // 判断是否能移动k步
        bool flag = false;
        for(int i = 0; i < k-1; i++) {
            if(end->next == nullptr) {
                flag = true;
                break;
            }
            end = end->next;
        }

        // 无法移动k步
        if(flag) {
            break;
        }
        // 可以走k步
        end = end->next;

        startPrev->next = reverseList(start, end);
        start->next = end;
        startPrev = start;
        start = end;
    }

    return dummy->next;
}

数组

区间查询计算——树状数组

307. 区域和检索 - 数组可修改

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
//需要注意的是，因为利用了位运算的奇技淫巧，所以树状数组需要从1开始
class NumArray {
public:
    //树状数组,https://oi-wiki.org/ds/fenwick/
    vector<int>bit;//bit[1....n] bit[1]表示a[0];bit[2]表示a[0]+a[1]; 管辖的区间是[x-lowbit(x),x-1]; 假设管辖的数组从0开始计数
    int lowbit(int x){
        // lowbit(0b01011000) == 0b00001000
        return x & -x;
    }
    // bit[0]..bit[x] 中间覆盖的点的和 相当于nums[0]+...+nums[x]
    int pre_sum(int x){
        int sum = 0;
        while(x >= 0){
            if(x==0){
                sum += bit[x];
                break;
            }
            sum += bit[x];
            x -= lowbit(x);
        }
        return sum;
    }    
    //单点加法，对于x加上y，更新所有的树状数组
    void add(int x, int y){
        while(x < bit.size()){
            bit[x] += y; 
            x += lowbit(x);
        }
    }
    //bit[left] 到 bit[right] 中间覆盖的点的和 nums[left]+...+nums[right]
    int get_sum(int left,int right){
        if(left>0)
        return pre_sum(right) - pre_sum(left-1);
        else{
            return pre_sum(right);
        }
    }
    NumArray(vector<int>& nums) {
        int n=nums.size();
        bit.resize(n,0);
        for(int i=0;i<n;i++){
            bit[i]+=nums[i];
            int t=i+lowbit(i);//树状数组性质:c[x]真包含于c[x+lowbit(x)]
            if(t<n)bit[t]+=bit[i];
        }
    }
    
    void update(int index, int val) {
        int old = sumRange(index, index);
        add(index, val-old);
    }
    
    int sumRange(int left, int right) {
        return get_sum(left, right);

    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 */

区间查询计算——线段树

307. 区域和检索 - 数组可修改

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//线段树
class SegmentTreeNode{
    public:
        SegmentTreeNode(int start,int end,int sum,SegmentTreeNode*left=nullptr,SegmentTreeNode*right=nullptr):start(start),end(end),sum(sum),left(left),right(right){};
        SegmentTreeNode(const SegmentTreeNode&) = delete;//禁用拷贝构造函数
        SegmentTreeNode& operator=(const SegmentTreeNode&) = delete;//禁用赋值   
        ~SegmentTreeNode(){
            delete left;
            delete right;
            left=right=nullptr;
        } 
    
    
    public:
        int start;
        int end;
        int sum;
    SegmentTreeNode*left;
    SegmentTreeNode*right;
    

};

class NumArray {
public:
    NumArray(vector<int>& nums) {
        _nums.assign(nums.begin(),nums.end());
        if(!_nums.empty()){
            _root=(buildTree(0,_nums.size()-1));
        }
    }
    
    void update(int index, int val) {
        updateTree(_root,index,val);

    }
    
    int sumRange(int left, int right) {
        return sumRange(_root,left,right);
    }
private:
    //线段树操作
    /*
        build(start,end,vals) O(n)
        update(index,value) O(logn)
        rangequery(start,end) O(logn+k) k表示会被的段的数量
    */
    vector<int>_nums;
    SegmentTreeNode*_root;

    SegmentTreeNode*buildTree(int start,int end){
        if(start==end){
            return new SegmentTreeNode(start,end,_nums[start]);
        }
        int mid=start+(end-start)/2;
        auto left=buildTree(start,mid);
        auto right=buildTree(mid+1,end);
        auto node=new SegmentTreeNode(start, end, left->sum + right->sum, left, right);
        return node;
    }
    void updateTree(SegmentTreeNode*root,int i,int val){
        if(root->start==i&&root->end==i){
            root->sum=val;
            return;
        }
        int mid=root->start+(root->end-root->start)/2;
        if(i<=mid){
            updateTree(root->left,i,val);
        }else{
            updateTree(root->right,i,val);
        }
        root->sum=root->left->sum+root->right->sum;
    }
    int sumRange(SegmentTreeNode*root,int i ,int j){
        if(i==root->start&&j==root->end){
            return root->sum;
        }
        int mid=root->start+(root->end-root->start)/2;
        if(j<=mid){
            return sumRange(root->left,i,j);
        }else if (i >mid){
            return sumRange(root->right,i,j);
        }else{
            return sumRange(root->left,i,mid)+sumRange(root->right,mid+1,j);
        }
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 */

搜索

排序

归并排序

统计逆序对

例题，剑指Offer51 https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

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
vector<int> temp;
int reverseCount;
void merge(vector<int>& nums, int al, int ar, int bl, int br) {
    int i = al, j = bl;
    int k = al;
    while(i <= ar && j <= br) {
        if(nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            reverseCount += ar - i + 1;
            temp[k++] = nums[j++];
        }
    }
    while(i <= ar) {
        temp[k++] = nums[i++];
    }
    while(j <= br) {
        temp[k++] = nums[j++];
    }
    for(k = al; k <= br; k++) {
        nums[k] = temp[k];
    }
}
void mergeSort(vector<int>& nums, int l, int r) {
    if(l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid+1, r);
    merge(nums, l, mid, mid+1, r);
}
int reversePairs(vector<int>& nums) {
    int n = nums.size();
    temp = vector<int>(n, 0);
    mergeSort(nums, 0, n-1);
    return reverseCount;
}

快速排序

求第K大

例题，LeetCode216 https://leetcode.cn/problems/kth-largest-element-in-an-array/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 统计nums[l, r]中的第k大
int findK(vector<int>& nums, int l, int r, int k) {
    int i = l - 1;
    int pivot = nums[r];
    for(int j = l; j <= r-1; j++) {
        if(nums[j] > pivot) {
            i++;
            swap(nums[j], nums[i]);
        }
    }
    swap(nums[i+1], nums[r]);
    // 分清楚i+1和k的关系
    if(i+1 - l + 1 == k) return nums[i+1];
    else if(i+1 - l + 1 > k) return findK(nums, l, i, k);
    else return findK(nums, i+2, r, k - (i+1 - l + 1));
}

图论

并查集

样例:leetcode 990 等式方程的可满足性

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
//count表示连通分量的个数，这里find使用了路径压缩，注意if语句而不是while;
class Solution {
public:
    //并查集
    //如果是等号，那么union；
    //如果是不等号，那么connect返回的值应该是false；
    vector<int>parent;
    int count;
    int find(int x){
        if(parent[x]!=x){
            parent[x]=find(parent[x]);
        }
        return parent[x];
    }
    void _union(int p,int q){
        int root_p=find(p);
        int root_q=find(q);
        if(root_p!=root_q){
            parent[root_p]=root_q;
            count--;
        }
        
        return;
    }
    bool connect(int p,int q){
        return find(p)==find(q);
    }
    bool equationsPossible(vector<string>& equations) {
        for(int i=0;i<26;i++){
            parent.emplace_back(i);
        }
        count=26;
        for(string now:equations){
            if(now[1]=='='){
                int a=now[0]-'a';
                int b=now[3]-'a';
                _union(a,b);
            }
        }
        for(string now:equations){
            if(now[1]=='!'){
                int a=now[0]-'a';
                int b=now[3]-'a';
                if(connect(a,b)){
                    return false;
                }
            }
        }
        return true;

    }
};

树

拓扑排序

Kruskal

Prim

树的直径

最短路

图遍历/环检测/拓扑排序

例题，207.课程表；另外拓扑排序相当于后序遍历加入的值(边表示依赖)(或者翻转后序遍历的值，边表示被依赖）210.课程表 II

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
//DFS版本
// 需要注意visited和onPath的顺序，如果onPath在循环内部，那么会错过根节点
// 记录被遍历过的节点
vector<bool> visited;
// 记录从起点到当前节点的路径
vector<bool> onPath;
bool hasCycle = false;
/* 图遍历框架 */
void traverse(vector<int>* graph, int s) {
    if (onPath[s]) {
        // 发现环！！！
        hasCycle = true;
    }
    if (visited[s] || hasCycle) {
        return;
    }
    // 将节点 s 标记为已遍历
    visited[s] = true;
    // 开始遍历节点 s
    onPath[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    // 节点 s 遍历完成
    onPath[s] = false;
}

Dijkstra

例题，LeetCode743 https://leetcode.cn/problems/network-delay-time/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 初始化
vector<bool> vis(n+1, false);
vector<int> dist(n+1, 0x3fffffff);
dist[st] = 0;
// 其实遍历n-1就可以
for(int i = 1; i <= n; i++) {
    // 寻找dist[u]最小且未被访问过的点
    int u = -1;
    for(int j = 1; j <= n; j++) {
        if(!vis[j] && (u == -1 || dist[j] < dist[u])) {
            u = j;
        }
    }
    // 根据dist[u]更新其邻点的dist
    vis[u] = true;
    for(auto&& [v, w] : g[u]) {
        dist[v] = min(dist[v], dist[u] + w);
    }
}

强连通分量

例题，POJ2186（貌似不支持C++11及其以上的语法） http://poj.org/problem?id=2186

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
void tarjan(int u) {
    dfn[u] = low[u] = ++timeStamp;
    
    // 入栈
    s.push(u);
    inStack[u] = true;
    
    for(auto&& v : g[u]) {
        if(dfn[v] == -1) { // 没有访问过的节点
            tarjan(v);
            low[u] = min(low[u], low[v]); // 如果v能够到达dfn更小的点，那么u也可以
        } else if(inStack[v]) { // v一定比u先被访问
            low[u] = min(low[u], dfn[v]); // 更新v能够到达的dfn更小的点
        }
    }

    // 缩点
    if(low[u] == dfn[u]) {
        ++sccCount;
        int x;
        do {
            x = s.top();
            s.pop();
            inStack[x] = false;
            node2scc[x] = sccCount;
            ++sccSize[sccCount];
        } while(x != u);
    }
}

二分图匹配（匈牙利算法）

1274 – The Perfect Stall (poj.org)

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
vector<vector<int> > g;
vector<int > x;
vector<int > y;
vector<bool > vis;
int n, m;

bool hungary(int u) {
	// u为X部的顶点
	// v为Y部的顶点
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (vis[v]) {
			continue;
		}
		vis[v] = true;
		// 如果Y部的顶点v还未被匹配，那么可以去匹配它
		// 假设v匹配了X部的顶点p，且从p能找到另一个匹配q，那么x-y-p-q是一条增广路径
		if (y[v] == -1 || hungary(y[v])) {
			x[u] = v;
			y[v] = u;
			return true;
		}
	}
	return false;
}

int main() {
	while (cin >> n >> m) {
		g = vector<vector<int> >(n, vector<int>(m, 0));
		vis = vector<bool >(m, false);
		x = vector<int >(n, -1);
		y = vector<int >(m, -1);

		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			while (x--) {
				int a;
				cin >> a;
				g[i].push_back(a - 1);
			}
		}

		int res = 0;
		for (int u = 0; u < n; u++) {
			// 如果X部还存在点未被匹配，那么尝试去匹配它
			if (x[u] == -1) {
				vis = vector<bool >(m + 1, false);
				if (hungary(u)) {
					res++;
				}
			}
		}

		cout << res << endl;
	}
	return 0;
}

最大流

题目P3376 【模板】网络最大流 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Edmod-Karp算法

其思想是使用bfs不断地找增广路，复杂度很高

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
int EdmodKarp(int source, int dest, vector<vector<ll>>& cap) {
	constexpr int maxFlow = 0x7fffffff;
	int n = cap.size();
	vector<int> pre(n, -1);

	auto bfs = [&]() {
		queue<int> q;
		pre = vector<int>(n, -1);
		vector<bool> vis(n, false);

		vis[source] = true;
		q.push(source);
		int flow = maxFlow;
		while (!q.empty()) {
			int u = q.front();
			q.pop();

			if (u == dest) {
				break;
			}

			for (int v = 0; v < n; v++) {
				if (cap[u][v] > 0 && !vis[v]) {
					vis[v] = true;
					pre[v] = u;
					if (flow > cap[u][v]) flow = cap[u][v];
					q.push(v);
				}
			}
		}

		if (pre[dest] == -1) {
			return 0;
		}
		else {
			return flow;
		}
	};

	int delta = 0;
	int sumFlow = 0;
	while (true) {
		delta = bfs();
		// delta不为0说明还能找到一条从source到dest的增广路径
		if (delta == 0) {
			break;
		}

		int cur = dest;
		while (pre[cur] != -1) {
			int last = pre[cur];
			cap[last][cur] -= delta;
			cap[cur][last] += delta;
			cur = last;
		}
		sumFlow += delta;
	}

	return sumFlow;
}

Ford-Fulkerson算法

将上述EK算法的bfs寻路改为dfs，即得到Ford-Fulkerson算法

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
using ll = long long;

ll FordFulkerson(int source, int dest, vector<vector<ll>>& cap) {
	constexpr ll maxFlow = 0x7fffffff;
	int n = cap.size();
	vector<bool> vis(n, false);

	auto dfs = [&](int cur, int des, ll curFlow) {
		function<ll(int, int, ll)> _dfs;

		_dfs = [&](int cur, int des, ll curFlow) -> ll {
			if (cur == des) {
				return curFlow;
			}
			vis[cur] = true;
			for (int v = 0; v < n; v++) {
				if (cap[cur][v] > 0 && !vis[v]) {
					ll flow = _dfs(v, des, min(curFlow, cap[cur][v]));
					if (flow > 0) {
						cap[cur][v] -= flow;
						cap[v][cur] += flow;
						return flow;
					}
				}
			}
			return 0;
		};

		return _dfs(cur, des, curFlow);
	};

	ll sumFlow = 0;
	while (true) {
		vis = vector<bool>(n, false);
		ll delta = dfs(source, dest, maxFlow);
		if (delta == 0) {
			break;
		}
		sumFlow += delta;
	}
	return sumFlow;
}

Dinic算法

首先使用bfs计算当前残差网络中每个节点的层次，然后使用dfs寻找增广路，要求在搜索过程中，深度为d的顶点只能走到深度为d+1的顶点

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
using ll = long long;

ll Dinic(int source, int dest, vector<vector<ll>>& cap) {
	constexpr ll maxFlow = 0x7fffffff;
	int n = cap.size();
	vector<int> depth(n, -1);

	auto dfs = [&](int cur, int des, ll curFlow) {
		function<ll(int, int, ll)> _dfs;

		_dfs = [&](int cur, int des, ll curFlow) -> ll {
			if (cur == des) {
				return curFlow;
			}
			for (int v = 0; v < n; v++) {
				if (cap[cur][v] > 0 && depth[v] == depth[cur] + 1) {
					ll flow = _dfs(v, des, min(curFlow, cap[cur][v]));
					if (flow > 0) {
						cap[cur][v] -= flow;
						cap[v][cur] += flow;
						return flow;
					}
				}
			}
			return 0;
		};

		return _dfs(cur, des, curFlow);
	};

	auto bfs = [&]() -> bool {
		queue<int> q;
		depth = vector<int>(n, -1);

		depth[source] = 1;
		q.push(source);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int v = 0; v < n; v++) {
				if (cap[u][v] > 0 && depth[v] == -1) {
					depth[v] = depth[u] + 1;
					q.push(v);
				}
			}
		}

		return depth[dest] != -1;
	};

	ll sumFlow = 0;
	while (bfs()) {
		while (true) {
			ll delta = dfs(source, dest, maxFlow);
			if (delta == 0) {
				break;
			}
			sumFlow += delta;
		}
	}
	return sumFlow;
}

最小费用最大流

题目P3381 【模板】最小费用最大流 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

在EK算法的基础上，求解增广路的同时求最短路（source到dest增广路径上的cost之和最小）

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

struct Edge {
	int u;
	int v;
	int cap;
	int cost;
	int next;
	Edge() = default;
	Edge(int _u, int _v, int _cap, int _cost, int _n) : u(_u), v(_v), cap(_cap), cost(_cost), next(_n) {}
};

struct Graph {
	vector<int> head;
	vector<Edge> edges;
	Graph() = delete;
	Graph(int n) : head(vector<int>(n, -1)) {}
	void AddEdge(int u, int v, int cap, int cost) {
		edges.emplace_back(u, v, cap, cost, head[u]);
		head[u] = edges.size() - 1;
	}
};

int spfa(int source, int dest, int n, Graph& g, vector<int>& pre, vector<int>& path, vector<int>& costSum) {
	constexpr int inf = 0x3fffffff;
	queue<int> q;
	vector<bool> inque(n ,false);
	pre = vector<int>(n, -1);
	path = vector<int>(n, -1);
	costSum = vector<int>(n, inf);
	vector<int> flow(n, 0);

	// 源点的流量初始为无穷大，cost为0
	q.push(source);
	inque[source] = true;
	flow[source] = inf;
	costSum[source] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		// 这里是spfa求最短路，不完全是一遍bfs
		inque[u] = false;

		for (int eid = g.head[u]; eid != -1; eid = g.edges[eid].next) {
			int v = g.edges[eid].v;
			int cost = g.edges[eid].cost;
			int cap = g.edges[eid].cap;
			// 松弛边
			if (g.edges[eid].cap > 0 && costSum[v] > costSum[u] + cost) {
				// 更新到v点的最小cost之和
				costSum[v] = costSum[u] + cost;
				// 更新到v点的最大流量
				flow[v] = min(flow[u], cap);
				// 记录到v点的上一个点和边号
				pre[v] = u;
				path[v] = eid;
				// spfa算法中v重新入队
				if (!inque[v]) {
					inque[v] = true;
					q.push(v);
				}
			}
		}
	}

	return flow[dest];
}

int mcmf(int source, int dest, int n, Graph& g) {
	vector<int> pre(n, -1);
	vector<int> path(n, -1);
	vector<int> costSum(n, 0);

	int minCost = 0;
	int maxFlow = 0;
	while (true) {
		// 运行一次最短路，求出增广路径上的流量
		int flow = spfa(source, dest, n, g, pre, path, costSum);
		if (flow == 0) {
			break;
		}
		// 更新最大流量和最小费用
		maxFlow += flow;
		minCost += flow * costSum[dest];
		// 更新残差网络
		int cur = dest;
		while (cur != source) {
			g.edges[path[cur]].cap -= flow;
			g.edges[path[cur] ^ 1].cap += flow;
			cur = pre[cur];
		}
	}

	cout << maxFlow << " " << minCost << endl;

	return minCost;
}

int main() {
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	Graph g(n);
	while (m--) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		// 正向边，capacity为c，cost为d
		g.AddEdge(a-1, b-1, c, d);
		// 反向边，capacity为0，cost为-d
		g.AddEdge(b-1, a-1, 0, -d);
	}
	mcmf(s-1, t-1, n, g);
	return 0;
}

动态规划

最长上升子序列

dp(i)表示长度为i+1的上升子序列的最后一位的最小值 https://leetcode.cn/problems/longest-increasing-subsequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    int len = 0;
    vector<int> dp(n, 0);
    dp[0] = nums[0];
    for(int i = 1; i < nums.size(); i++) {
        if(dp[len] < nums[i]) {
            dp[++len] = nums[i];
        } else {
            auto it = lower_bound(dp.begin(), dp.begin() + len + 1, nums[i]);
            *it = nums[i];
        }
    }
    return len + 1;
}

不同的子序列

给定字符串s和t，计算s子序列中t出现的次数。首先在s和t前面加上一个标记字符，然后dp(i, j)表示s[1…i]的子序列中t[1…j]出现的次数。 https://leetcode.cn/problems/distinct-subsequences/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int numDistinct(string s, string t) {
    s = "#" + s;
    t = "#" + t;
    int lens = s.size();
    int lent = t.size();
    vector<vector<unsigned long long>> dp(lens, vector<unsigned long long>(lent, 0));
    
    for(int i = 0; i < lens; i++) dp[i][0] = 1;
    for(int i = 1; i < lens; i++) {
        for(int j = 1; j < lent; j++) {
            if(s[i] == t[j]) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    return dp[lens - 1][lent - 1];
}

最长回文子序列

dp(i, j)表示s[i…j]中的最长回文子序列的长度，分情况讨论s[i]是否等于s[j]即可。 https://leetcode.cn/problems/longest-palindromic-subsequence/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for(int i = 0; i < n; i++) {
        dp[i][i] = 1;
        if(i < n-1)  {
            if(s[i] == s[i+1])
                dp[i][i+1] = 2;
            else
                dp[i][i+1] = 1;
        }
    }
    for(int i = n-1; i >= 0; i--) {
        for(int j = i + 2; j < n; j++) {
            if(s[i] == s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1];
}

数位dp

树状dp

例题,leetcode 834 树中距离之和,换根DP，原理是当根发生变化的时候只有部分状态需要修改

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
//result数组保存第i个节点到所有其他节点的距离之和
//dp[i] 表示以0为根节点的情况下，以i节点为根的子树中，i节点到它的子孙的距离之和
//size[i] 表示i节点为根的子树的点的数量
//初始情况下dp[i]=0 size[i]=1
//样例中dp[0]=dp[1]+size[1]+dp[2]+size[2]=0+1+3+4=8

class Solution {
public:
    vector<int>dp;
    vector<int>size;
    vector<int>result;
    void dfs(vector<vector<int>>&graph,int now,int father){
        size[now]=1;
        dp[now]=0;
        for(int node:graph[now]){
            if(node!=father){
                dfs(graph,node,now);
                dp[now]=dp[now]+dp[node]+size[node];
                size[now]=size[node]+size[now];
            }
        }
    }
    void solve(vector<vector<int>>&graph,int now,int father){
        result[now]=dp[now];
        for(int node:graph[now]){
            if(node!=father){
                //换根 主要原理是很多点的状态不需要修改
                //首先保留原来的状态
                int dp_now=dp[now],size_now=size[now],dp_node=dp[node],size_node=size[node];
                //状态转移 假设以node为根，进行求解;
                dp[now]=dp[now]-(dp[node]+size[node]);
                size[now]=size[now]-size[node];
                dp[node]=dp[node]+dp[now]+size[now];
                size[node]=size[node]+size[now];
                solve(graph,node,now);
                //还原现场
                dp[now]=dp_now;
                dp[node]=dp_node;
                size[now]=size_now;
                size[node]=size_node;
            }
        }
    }
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        vector<vector<int>>graph(n,vector<int>());
        dp.resize(n,0);
        size.resize(n,0);
        result.resize(n,0);
        for(vector<int>_pair:edges){
            int u=_pair[0];
            int v=_pair[1];
            graph[u].emplace_back(v);
            graph[v].emplace_back(u);
        }
        dfs(graph,0,-1);//从0这个根节点开始做预处理;
        solve(graph,0,-1);
        
        return result;
    }
};

字符串

字典树

Rabin-Karp (Hash)

Knuth-Morris-Pratt

数学

GCD 最大公约数

914. 卡牌分组，365. 水壶问题， 1071. 字符串的最大公因子

1
2
3
4
5
6
7
int _gcd(int a,int b){
        //gcd(a,b)=gcd(b,a%b);
        if(b==0){
            return a;
        }
        return _gcd(b,a%b);
    }

优质算法博客

  1. 木易東
  2. labuladong
  3. OI wiki
  4. 几乎刷完了力扣所有的堆题，我发现了这些东西。。。