# codeBook
``` c++
#include <sstream>
getline(cin, str);
stringstream ss;
ss << str;
vector<int> p;
while (ss >> m) p.push_back(m);
```
``` c++
#include<iomanip>
cout << setw(4) << output;
```
``` c++
#include <iostream>
#include <vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}
```
priority_queue：優先隊列，資料預設由大到小排序，即優先權高的資料會先被取出。
宣告：
priority_queue <int> pq;
把元素 x 加進 priority_queue：
pq.push(x);
讀取優先權最高的值：
x = pq.top();
pq.pop(); // 讀取後刪除
pq.empty() 回傳true
pq.size() 回傳零
如需改變priority_queue的優先權定義：
* priority_queue<T> pq; 預設由大排到小
* priority_queue<T, vector<T>, greater<T> > pq; 改成由小排到大
* priority_queue<T, vector<T>, cmp> pq; 自行定義 cmp 排序
ZzKKu3
LCS
``` c++
vector<vector<int> >dp(str1.length() + 1, vector<int>(str2.length() + 1, 0));
for(int i = 1; i <= str1.length(); i++) {
for(int j = 1; j <= str2.length(); j++) {
if(str1[i - 1] == str2[j - 1]) {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + 1);
} else {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
for(int i = 1; i <= str1.length(); i++) {
for(int j = 1; j <= str2.length(); j++) {
cout << dp[i][j] << " ";
}
cout << endl;
}
```
Greedy
``` c++
vector<vector<int> > dp(n, vector<int>(n, 0));
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(j - i == 2)
dp[i][j] = v[j - 2] * v[j - 1] * v[j];
if(j - i > 2)
dp[i][j] = INT32_MAX;
}
}
for(int i = n - 1; i >= 0; i--) {
for(int j = 0; j < n; j++) {
for(int k = i + 1; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] +v[i] * v[j] * v[k]);
}
}
}
```
``` c++
sort(v.begin(), v.end());
for(int i = 1; i <= k; i++) {
for(int j = 1; j <= n; j++) {
int z;
for(z = 1; z < j; z++) {
if(v[j] - v[z] <= 5)
break;
}
dp[i][j] = max(dp[i][j - 1], dp[i - 1][z - 1] + (j - z + 1));
}
}
```
無限背包
``` c++
sort()
for(int i = 1; i < dp.size(); i++) {
dp[i] = unit * i;
for(int j = 0; j < v.size(); j++) {
if(v[j].first > i)
break;
dp[i] = min(dp[i - v[j].first] + v[j].second, dp[i]);
}
```
01 背包
``` c++
for( int i = 1 ; i <= n; i++ ){
for( int j = 1 ; j <= num ; j++ ){
if( v[j] <= i ) dp[i][j] = max( dp[i-v[j]][j-1]+v[j], dp[i][j-1] );
else dp[i][j] = dp[i][j-1];
}
}
```
``` c++
vector<long long> dp(3, 0);
long long best = 0;
for(int i = 0; i < n; i++) {
cin >> v[i];
// (沒乘 ＋ 有乘 or 有乘 ＋ 有乘 or 新的有乘 在加沒乘) or 新的沒乘
dp[2] = max(dp[1] + v[i], max(dp[2] + v[i], v[i]));
// 沒乘 ＋ 有乘 or 有乘 ＋ 有乘 or 新的有乘
dp[1] = max(dp[0] + x * v[i], max(dp[1] + x * v[i], x * v[i]));
// 沒乘 ＋ 沒乘 or 新的沒乘
dp[0] = max(dp[0] + v[i], v[i]);
best = max(best, max(dp[2], max(dp[1], dp[0])));
}
```
``` c++
void pull(int x) {
total[x] = total[x << 1] + total[x << 1|1];
}
void build(int x, int l, int r) {
if(l == r) {
total[x] = 1;
return;
}
int mid = (l + r) >> 1;
build(x << 1, l, mid);
build(x << 1|1, mid + 1, r);
pull(x);
}
int query(int x, int l, int r, int ql, int qr) {
if(ql <= l && qr >= r)
return total[x];
int ret = 0;
int mid = (l + r) >> 1;
if(ql <= mid) {
ret += query(x<<1, l, mid, ql, qr);
}
if(qr > mid) {
ret += query(x<<1|1, mid + 1, r, ql, qr);
}
return ret;
}
void update(int x, int l, int r, int pos, int val){
if (l == r){
total[x] = val;
return;
}
int mid = (l+r) >> 1;
if (pos <= mid) update(x<<1, l, mid, pos, val);
else update(x<<1|1, mid+1, r, pos, val);
pull(x);
}
int main() {
build(1, 1, 8);
update(1, 1, 8, 8, 2);
for(int i = 0; i < 30; i++) {
cout << total[i] << " ";
}
}
```
```
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<queue>
using namespace std;
int day, n, k;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> day >> n >> k;
long long max = 0;
vector<vector<long long>> v(day + 2, vector<long long>(3, 0));
for(int i = 0; i < n; i++) {
int c, b, e;
cin >> c >> b >> e;
for(int j = b; j <= e; j++) {
if(v[j][0] == k) {
if(v[j][1] < c) {
v[j][2] -= v[j][1];
v[j][2] += c;
v[j][1] = c;
}
} else {
if(v[j][1] > c || v[j][0] == 0) {
v[j][1] = c;
}
v[j][2] += c;
v[j][0] ++;
}
max = v[j][2] > max ? v[j][2] : max;
}
}
cout << max;
}
```
## Graph
### DFS
1. Tree edge：若vertex(Y)是被vertex(X)「發現」，則edge(X,Y)即為Tree edge，也就是Depth-First Tree中的edge。
透過顏色判斷edge：當vertex(X)搜尋到vertex(Y)，且vertex(Y)為「白色」時，就會建立出Tree edge。
2. Back edge：所有指向ancestor的edge，稱為Back edge。如圖六中，edge(F,B)與edge(H,G)。
透過顏色判斷edge：當vertex(X)搜尋到vertex(Y)，且vertex(Y)為「灰色」，就會建立起Back edge，見圖三(j)、圖三(q)與圖六。
3. Forward edge：所有指向descendant但不是Tree edge的edge，稱為Forward edge。觀察「時間軸」，若Graph存在例如：edge(A,D)、edge(A,E)或者edge(B,E)，即可稱之為Forward edge。很遺憾的，圖六中，沒有Forward edge。
透過顏色判斷edge：當vertex(X)搜尋到vertex(Y)時，vertex(Y)為「黑色」，並且discover[X]<discover[Y]，edge(X,Y)即為Forward edge。
4. Cross edge：若兩個vertex 不在同一棵Depth-First Tree上，例如vertex(C)與vertex(H)，或者兩個vertex在同一棵Depth-First Tree上卻沒有「ancestor-descendant」的關係，例如vertex(C)與vertex(F)，則稱連結此兩個vertex的edge為Cross edge。
透過顏色判斷edge：當vertex(X)搜尋到vertex(Y)時，vertex(Y)為「黑色」，並且discover[X]>discover[Y]，edge(X,Y)即為Cross edge。
``` c
void DFS(int vertex, int &time, vector<vector<int> > &adj, vector<int> &discover, vector<int> &color, vector<int> &finish, vector<queue <int> > &q){
if(color[vertex] == 2)
return;
if(color[vertex] == 0) {
color[vertex] = 1;
discover[vertex] = time;
time ++;
for(int i = 0; i < 8; i++) {
if(adj[vertex][i] && color[i] == 0){
q[vertex].push(i);
}
}
while(!q[vertex].empty()) {
int cur = q[vertex].front();
q[vertex].pop();
DFS(cur, time, adj, discover, color, finish, q);
}
}
if(color[vertex] == 1) {
color[vertex] = 2;
finish[vertex] = time;
time ++;
}
}
```
### Bellman-Ford
```c
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define P pair<long long, int>
int main() {
vector<P> G[5];
G[0].push_back(P(3, 4));
G[0].push_back(P(10, 1));
G[1].push_back(P(4, 4));
G[1].push_back(P(2, 2));
G[2].push_back(P(9, 3));
G[3].push_back(P(7, 2));
G[4].push_back(P(1, 1));
G[4].push_back(P(8, 2));
G[4].push_back(P(2, 3));
long long dist[5];
for(int i = 0; i < 5; i++) {
dist[i] = 1000000;
}
dist[0] = 0;
for(int j = 0; j < 5; j++){
for(int i = 0; i < 5; i++){
for (auto nxt: G[i]){
if (dist[nxt.second] > dist[i] + nxt.first){
dist[nxt.second] = dist[i] + nxt.first;
}
}
for(int i = 0; i < 5; i++) {
cout << dist[i] << " ";
}
cout << endl;
}
}
}
```
### DijkstraAlgorithm
``` c
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define P pair<long long, int>
int main() {
vector<P> G[5];
G[0].push_back(P(3, 4));
G[0].push_back(P(10, 1));
G[1].push_back(P(4, 4));
G[1].push_back(P(2, 2));
G[2].push_back(P(9, 3));
G[3].push_back(P(7, 2));
G[4].push_back(P(1, 1));
G[4].push_back(P(8, 2));
G[4].push_back(P(2, 3));
priority_queue<P, vector<P>, greater<P> > pq;
long long dist[5];
for(int i = 0; i < 5; i++) {
dist[i] = 1000000;
}
dist[0] = 0;
pq.push(P(0, 0));
while (!pq.empty()){
P p = pq.top();
pq.pop();
for (auto nxt: G[p.second]){
if (dist[p.second] < p.first) continue;
if (dist[nxt.second] > dist[p.second] + nxt.first){
dist[nxt.second] = dist[p.second] + nxt.first;
pq.push(P(dist[nxt.second], nxt.second));
}
}
for(int i = 0; i < 5; i++) {
cout << dist[i] << " ";
}
cout << endl;
}
}
```
### Floyd–WarshallAlgorithm
``` c
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define P pair<long long, int>
int main() {
vector<vector<int> > G;
G.push_back(vector<int>{0, 2, 6, 4});
G.push_back(vector<int>{1000000, 0, 3, 1000000});
G.push_back(vector<int>{7, 1000000, 0, 1});
G.push_back(vector<int>{5, 1000000, 12, 0});
for(int k = 0; k < 4; k++) {
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if(G[i][j] > G[i][k] + G[k][j]) {
G[i][j] = G[i][k] + G[k][j];
}
}
}
}
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
cout << G[i][j] << " ";
}
cout << endl;
}
}
```
### Kruskal'sAlgorithm
``` c
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
using namespace std;
class DSU
{
int *parent;
int *rank;
public:
DSU(int n)
{
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++)
{
parent[i] = -1;
rank[i] = 1;
}
}
// Find function
int find(int i)
{
if (parent[i] == -1)
return i;
return parent[i] = find(parent[i]);
}
// union function
void unite(int x, int y)
{
int s1 = find(x);
int s2 = find(y);
if (s1 != s2)
{
if (rank[s1] < rank[s2])
{
parent[s1] = s2;
rank[s2] += rank[s1];
}
else
{
parent[s2] = s1;
rank[s1] += rank[s2];
}
}
}
};
class Graph
{
vector<tuple<int, int, int>> edgelist;
int V;
public:
Graph(int V)
{
this->V = V;
}
void addEdge(int x, int y, int w)
{
edgelist.push_back({w, x, y});
}
int kruskals_mst()
{
// 1. Sort all edges
sort(edgelist.begin(), edgelist.end());
// Initialize the DSU
DSU s(V);
int ans = 0;
for (auto edge : edgelist)
{
int w = get<0>(edge);
int x = get<1>(edge);
int y = get<2>(edge);
// take that edge in MST if it does form a cycle
if (s.find(x) != s.find(y))
{
s.unite(x, y);
ans += w;
}
}
return ans;
}
};
int main()
{
int n, m;
cin >> n >> m;
Graph g(n);
for (int i = 0; i < m; i++)
{
int x, y, w;
cin >> w >> x >> y;
g.addEdge(x, y, w);
}
cout << g.kruskals_mst();
return 0;
}
```
#### Version 2
``` c
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class DSU
{
int *parent;
int *rank;
public:
DSU(int n)
{
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++)
{
parent[i] = -1;
rank[i] = 1;
}
}
// Find function
int find(int i)
{
if (parent[i] == -1)
return i;
return parent[i] = find(parent[i]);
}
// union function
void unite(int x, int y)
{
int s1 = find(x);
int s2 = find(y);
if (s1 != s2)
{
if (rank[s1] < rank[s2])
{
parent[s1] = s2;
rank[s2] += rank[s1];
}
else
{
parent[s2] = s1;
rank[s1] += rank[s2];
}
}
}
};
class Graph
{
vector<vector<int>> edgelist;
int V;
public:
Graph(int V)
{
this->V = V;
}
void addEdge(int x, int y, int w)
{
edgelist.push_back({w, x, y});
}
int kruskals_mst()
{
// 1. Sort all edges
sort(edgelist.begin(), edgelist.end());
// Initialize the DSU
DSU s(V);
int ans = 0;
for (auto edge : edgelist)
{
int w = edge[0];
int x = edge[1];
int y = edge[2];
// take that edge in MST if it does form a cycle
if (s.find(x) != s.find(y))
{
s.unite(x, y);
ans += w;
}
}
return ans;
}
};
int main()
{
int n, m;
cin >> n >> m;
Graph g(n);
for (int i = 0; i < m; i++)
{
int x, y, w;
cin >> w >> x >> y;
g.addEdge(x, y, w);
}
cout << g.kruskals_mst();
return 0;
}
```
## maxFlow
add_edge 要從 bgm->add_edge(from, to, cap)
```c=
#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
#define MAXN 1000
#define INF 10
using namespace std;
typedef struct MaxFlow mf;
struct MaxFlow{
struct edge{
int to, cap, flow, rev;
};
vector<edge> v[MAXN];
int s, t, dis[MAXN], cur[MAXN];
int dfs(int u, int cap){
if(u == t || !cap)
return cap;
for(int &i = cur[u]; i < v[u].size(); i++){
edge &e = v[u][i];
if(dis[e.to] == dis[u] + 1 && e.flow != e.cap){
int df = dfs(e.to, min(e.cap - e.flow, cap));
if(df){
e.flow += df;
v[e.to][e.rev].flow -= df;
return df;
}
}
}
dis[u] = -1;
return 0;
}
bool bfs(){
memset(dis, -1, sizeof(dis));
queue<int> q;
q.push(s), dis[s] = 0;
while(!q.empty()){
int tmp = q.front();
q.pop();
for(auto &u : v[tmp]){
if(!~dis[u.to] && u.flow != u.cap){
q.push(u.to);
dis[u.to] = dis[tmp] + 1;
}
}
}
return dis[t] != -1;
}
int maxflow(int _s, int _t){
s = _s, t = _t;
int flow = 0, df;
while(bfs()){
memset(cur, 0, sizeof(cur));
df = dfs(s, INF);
while(df){
flow += df;
df = dfs(s, INF);
}
}
return flow;
}
void addedge(int st, int ed, int cap){
v[st].push_back(edge{ed, cap, 0, (int)v[ed].size()});
v[ed].push_back(edge{st, 0, 0, (int)v[st].size() - 1});
}
};
int main() {
mf *maxF = new MaxFlow();
maxF->addedge(0, 1, 2);
maxF->addedge(1, 2, 2);
maxF->addedge(2, 3, 2);
maxF->addedge(0, 4, 3);
maxF->addedge(4, 5, 3);
maxF->addedge(5, 3, 3);
maxF->addedge(3, 4, 2);
cout << maxF->maxflow(0, 3) << endl;
}
```
## matching
add_edge 要從 bgm->add_edge(小, 大)
```c=
#include<iostream>
#include<vector>
#include<bitset>
#include<memory.h>
#define MAXN 1000
using namespace std;
typedef struct Bipartite_Graph_Matching BGM;
struct Bipartite_Graph_Matching{
int mp[MAXN + 1], mq[MAXN + 1], n;
bitset<MAXN + 1> vis;
vector<int> child[MAXN + 1];
void init(int _n){
n = _n;
for(int i = 1; i <= n; i++)
child[i].clear();
}
void add_edge(int x, int y){
child[x].push_back(y);
}
bool dfs(int x){
vis[x] = 1;
for(int i : child[x])
if(!~mq[i] || !vis[mq[i]] && dfs(mq[i]))
return mq[mp[x] = i] = x, 1;
return 0;
}
int matching(){
int ans = 0;
memset(mp, -1, sizeof(mp)), memset(mq, -1, sizeof(mq));
for(int i = 1; i <= n; i++)
if(vis.reset(), dfs(i))
ans++;
return ans;
}
};
int main() {
BGM *bgm = new BGM();
bgm->init(6);
bgm->add_edge(1, 4);
// bgm->add_edge(1, 5);
// bgm->add_edge(1, 6);
bgm->add_edge(2, 4);
bgm->add_edge(2, 5);
// bgm->add_edge(2, 6);
bgm->add_edge(3, 4);
bgm->add_edge(3, 5);
bgm->add_edge(3, 6);
cout << bgm->matching();
}
```
Sign in with Wallet
Connect another wallet