* ---
tags: 高階競技程式設計
---
# Codebook team21_23
## Initial
```C++=
#include<bits/stdc++.h>
#include<numeric>
using namespace std;
int main()
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}
```
再新增
## Containers
### vector
vector<int> vec(3, 0) - 三個0
vector<T> v(n);
vector<T> v;
vec[i] - 存取索引值為 i 的元素值。
vec.at(i) - 存取索引值為 i 的元素的值，
vec.front() - 回傳 vector 第一個元素的值。
vec.back() - 回傳 vector 最尾元素的值。
vec.push_back(val) - 新增元素至 vector 的尾端，必要時會進行記憶體配置。
vec.pop_back() - 刪除 vector 最尾端的元素。
vec.insert(position,value) - 插入一個或多個元素至 vector 內的任意位置。
vec.erase() - 刪除 vector 中一個或多個元素。
vec.clear() - 清空所有元素。
vec.empty() - 如果 vector 內部為空，則傳回 true 值。
vec.size() - 取得 vector 目前持有的元素個數。
v.resize(n) - 把 vector 的大小調整為 n
v.assign(n, val) - 把 vector 的內容改為 n 個元素，且元素的值為 val
### 其他
WEEK2 課程教材中
## Tool
### string內字母分開存進array
```C++=
char a[];
string str;cin>>str;
int x;x=0;
for(char w:str){
a[x] = w;
x++;
}
```
### 左移陣列
```C++=
rotate(arr.begin(),arr.begin()+d,arr.end())
```
#include <algorithm>
i 選取起始位置 , d 左移次數 , j 選取結束位置
### 右移陣列
```C++=
rotate(arr.begin(),arr.begin()+j-i+1-d ,arr.end())
```
### Array總和
```C++=
accumulate(arr.begin(), arr.end(),0)
```
#include <numeric>
第三項為初始值，一般為0
### Sort
```C++=
bool compare(int a, int b) {
return a > b;
}
sort(arr,arr+x);
sort(arr,arr+x,compare);
//降冪
```
### 多維Sort
```C++=
for(int i=n-1;i>0;i--){
for(int j=0;j<=i-1;j++){
if(a[j][1]>a[j+1][1]){
int t1=a[j][0];
int t2=a[j][1];
a[j][0]=a[j+1][0];
a[j][1]=a[j+1][1];
a[j+1][0]=t1;
a[j+1][1]=t2;
}
}
}
```
視維度增加temp
### Sort 一維陣列(2-block)
```C++=
void sort(int row, int n){
char t1, t2;
for(int j=n-1;j>0;j--){
for(int i=0;i<=j-1;i++){
if(work[row][2*i+2] > work[row][2*i+4]){
t1 = work[row][2*i+1];
t2 = work[row][2*i+2];
work[row][2*i+1] = work[row][2*i+3];
work[row][2*i+2] = work[row][2*i+4];
work[row][2*i+3] = t1;
work[row][2*i+4] = t2;
}
}
}
}
```
### char陣列 轉int
```C++=
for (int i = 0; i < x; i++) {
int ia =(int)a[i];
s[i]=ia-48;
}
```
## Basic
### vimrc
```C++=
=== .vimrc ===
set et nu cin ls=2 ts=4 sw=4 sts=4 ttm=100
syntax on
nn <F4> :w ! cat -n \| lpr <CR>
nn <F7> :w <bar> :!vim %<_.in<left><left><left>
nn <F8> :w <bar> :!g++ % -o %< -std=c++11
\ -fsanitize=undefined -Wall -Wextra -Wshadow -DFOX &&
\ for i in %<_*.in; do echo == && ./%< < $i; done <CR>
nn <F9> :w <bar> :!g++ % -o %< -std=c++11
\ -fsanitize=undefined -Wall -Wextra -Wshadow -DFOX &&
\ echo == && ./%<
```
### default code
```C++=
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <sys/time.h>
#include <sys/resource.h>
using namespace std;
void setstack(){
// Set soft limit and hard limit to max
const rlimit tmp {RLIM_INFINITY ,RLIM_INFINITY};
setrlimit(RLIMIT_STACK ,&tmp);
}
int main(){
#define name ""
#ifndef FOX
freopen(name".in","r",stdin);
freopen(name".out","w",stdout);
#endif
static_assert(strlen(name));
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
}
```
## Flow
### Dinic
(a) Bounded Maxflow Construction:
1. add two node ss, tt
2. add_edge(ss, tt, INF)
3. for each edge u -> v with capacity [l, r]:
add_edge(u, tt, l)
add_edge(ss, v, l)
add_edge(u, v, r-l)
4. see (b), check if it is possible.
5. answer is maxflow(ss, tt) + maxflow(s, t)
-------------------------------------------------------
(b) Bounded Possible Flow:
1. same construction method as (a)
2. run maxflow(ss, tt)
3. for every edge connected with ss or tt:
rule: check if their rest flow is exactly 0
4. answer is possible if every edge do satisfy the rule
;
5. otherwise, it is NOT possible.
-------------------------------------------------------
(c) Bounded Minimum Flow:
1. same construction method as (a)
2. answer is maxflow(ss, tt)
-------------------------------------------------------
(d) Bounded Minimum Cost Flow:
* the concept is somewhat like bounded possible flow.
1. same construction method as (a)
2. answer is maxflow(ss, tt) + (∑ l * cost for every
edge)
-------------------------------------------------------
(e) Minimum Cut:
1. run maxflow(s, t)
2. run cut(s)
3. ss[i] = 1: node i is at the same side with s.
-------------------------------------------------------
```C++=
const long long INF = 1LL<<60;
struct Dinic { //O(VVE), with minimum cut
static const int MAXN = 5003;
struct Edge{
int u, v;
long long cap, rest;
};
int n, m, s, t, d[MAXN], cur[MAXN];
vector<Edge> edges;
vector<int> G[MAXN];
void init(){
edges.clear();
for ( int i = 0 ; i < n ; i++ ) G[i].clear();
n = 0;
}
// min cut start
bool side[MAXN];
void cut(int u) {
side[u] = 1;
for ( int i : G[u] ) {
if ( !side[ edges[i].v ] && edges[i].rest )
cut(edges[i].v);
}
}
// min cut end
int add_node(){
return n++;
}
void add_edge(int u, int v, long long cap){
edges.push_back( {u, v, cap, cap} );
edges.push_back( {v, u, 0, 0LL} );
m = edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool bfs(){
fill(d,d+n,-1);
queue<int> que;
que.push(s); d[s]=0;
while (!que.empty()){
int u = que.front(); que.pop();
for (int ei : G[u]){
Edge &e = edges[ei];
if (d[e.v] < 0 && e.rest > 0){
d[e.v] = d[u] + 1;
que.push(e.v);
}
}
}
return d[t] >= 0;
}
long long dfs(int u, long long a){
if ( u == t || a == 0 ) return a;
long long flow = 0, f;
for ( int &i=cur[u]; i < (int)G[u].size() ; i++) {
Edge &e = edges[ G[u][i] ];
if ( d[u] + 1 != d[e.v] ) continue;
f = dfs(e.v, min(a, e.rest) );
if ( f > 0 ) {
e.rest -= f;
edges[ G[u][i]^1 ].rest += f;
flow += f;
a -= f;
if ( a == 0 )break;
}
}
return flow;
}
long long maxflow(int _s, int _t){
s = _s, t = _t;
long long flow = 0, mf;
while ( bfs() ){
fill(cur,cur+n,0);
while ( (mf = dfs(s, INF)) ) flow += mf;
}
return flow;
}
} dinic;
```
### GomoryHu tree
-------------------------------------------------------
Construct of Gomory Hu Tree
1. make sure the whole graph is clear
2. set node 0 as root, also be the parent of other nodes.
3. for every node i > 0, we run maxflow from i to parent[i]
4. hense we know the weight between i and parent[i]
5. for each node j > i, if j is at the same side with i , make the parent of j as i
-------------------------------------------------------
```C++=
int e[MAXN][MAXN];
int p[MAXN];
Dinic D; // original graph
void gomory_hu() {
fill(p, p+n, 0);
fill(e[0], e[n], INF);
for ( int s = 1 ; s < n ; s++ ) {
int t = p[s];
Dinic F = D;
int tmp = F.max_flow(s, t);
for ( int i = 1 ; i < s ; i++ )
e[s][i] = e[i][s] = min(tmp, e[t][i]);
for ( int i = s+1 ; i <= n ; i++ )
if ( p[i] == t && F.side[i] ) p[i] = s;
}
}
```
### min cost flow
```C++=
// long long version
typedef pair<long long, long long> pll;
struct CostFlow {
static const int MAXN = 350;
static const long long INF = 1LL<<60;
struct Edge {
int to, r;
long long rest, c;
};
int n, pre[MAXN], preL[MAXN]; bool inq[MAXN];
long long dis[MAXN], fl, cost;
vector<Edge> G[MAXN];
void init() {
for ( int i = 0 ; i < MAXN ; i++) G[i].clear();
}
void add_edge(int u, int v, long long rest, long long c) {
G[u].push_back({v, (int)G[v].size(), rest, c});
G[v].push_back({u, (int)G[u].size()-1, 0, -c});
}
pll flow(int s, int t) {
fl = cost = 0;
while (true) {
fill(dis, dis+MAXN, INF);
fill(inq, inq+MAXN, 0);
dis[s] = 0;
queue<int> que;
que.push(s);
while ( !que.empty() ) {
int u = que.front(); que.pop();
inq[u] = 0;
for ( int i = 0 ; i < (int)G[u].size(); i++) {
int v = G[u][i].to;
long long w = G[u][i].c;
if ( G[u][i].rest > 0 && dis[v] >
dis[u] + w) {
pre[v] = u; preL[v] = i;
dis[v] = dis[u] + w;
if (!inq[v]) {
inq[v] = 1;
que.push(v);
}
}
}
}
if (dis[t] == INF) break;
long long tf = INF;
for (int v = t, u, l ; v != s ; v = u ) {
u = pre[v]; l = preL[v];
tf = min(tf, G[u][l].rest);
}
for (int v = t, u, l ; v != s ; v = u ) {
u = pre[v]; l = preL[v];
G[u][l].rest -= tf;
G[v][G[u][l].r].rest += tf;
}
cost += tf * dis[t];
fl += tf;
}
return {fl, cost};
}
} flow;
```
### SW mincut 全點對最小割
```C++=
// all pair min cut
// global min cut
struct SW{ // O(V^3)
static const int MXN = 514;
int n,vst[MXN],del[MXN];
int edge[MXN][MXN],wei[MXN];
void init(int _n){
n = _n; FZ(edge); FZ(del);
}
void addEdge(int u, int v, int w){
edge[u][v] += w; edge[v][u] += w;
}
void search(int &s, int &t){
FZ(vst); FZ(wei);
s = t = -1;
while (true){
int mx=-1, cur=0;
for (int i=0; i<n; i++)
if (!del[i] && !vst[i] && mx<wei[i])
cur = i, mx = wei[i];
if (mx == -1) break;
vst[cur] = 1;
s = t; t = cur;
for (int i=0; i<n; i++)
if (!vst[i] && !del[i]) wei[i] += edge[cur][i];
}
}
int solve(){
int res = 2147483647;
for (int i=0,x,y; i<n-1; i++){
search(x,y);
res = min(res,wei[y]);
del[y] = 1;
for (int j=0; j<n; j++)
edge[x][j] = (edge[j][x] += edge[y][j]);
}
return res;
}
}graph;
```
## Matching
### Hungarian
```C++=
// Maximum Cardinality Bipartite Matching
// Worst case O(nm)
struct Graph{
static const int MAXN = 5003;
vector<int> G[MAXN];
int n, match[MAXN], vis[MAXN];
void init(int _n){
n = _n;
for (int i=0; i<n; i++) G[i].clear();
}
bool dfs(int u){
for (int v:G[u]){
if (vis[v]) continue;
vis[v]=true;
if (match[v]==-1 || dfs(match[v])){
match[v] = u;
match[u] = v;
return true;
}
}
return false;
}
int solve(){
int res = 0;
memset(match,-1,sizeof(match));
for (int i=0; i<n; i++){
if (match[i]==-1){
memset(vis,0,sizeof(vis));
if ( dfs(i) ) res++;
}
}
return res;
}
} graph;
```
### KM
```C++=
const int MAXN = 400 + 10;
const long long INF64 = 0x3f3f3f3f3f3f3f3fll;
int nl, nr;
int pre[MAXN];
long long slack[MAXN];
long long W[MAXN][MAXN];
long long lx[MAXN], ly[MAXN];
int mx[MAXN], my[MAXN];
bool vx[MAXN], vy[MAXN];
void augment(int u) {
if(!u) return;
augment(mx[pre[u]]);
mx[pre[u]] = u;
my[u] = pre[u];
}
void match(int x) {
queue<int> que;
que.push(x);
while(1) {
while(!que.empty()) {
x = que.front(); que.pop();
vx[x] = 1;
for (int i=1; i<=nr; i++) {
if(vy[i]) continue;
long long t = lx[x] + ly[i] - W[x][i];
if(t > 0) {
if(slack[i] >= t) slack[i] = t, pre
[i] = x;
continue;
}
pre[i] = x;
if(!my[i]) {
augment(i);
return;
}
vy[i] = 1;
que.push(my[i]);
}
}
long long t = INF64;
for (int i=1; i<=nr; i++) if(!vy[i]) t = min(t,slack[i]);
for (int i=1; i<=nl; i++) if(vx[i]) lx[i] -= t;
for (int i=1; i<=nr; i++) {
if(vy[i]) ly[i] += t;
else slack[i] -= t;
}
for (int i=1; i<=nr; i++) {
if(vy[i] || slack[i]) continue;
if(!my[i]) {
augment(i);
return;
}
vy[i] = 1;
que.push(my[i]);
}
}
}
int main() {
int m;
cin >> nl >> nr >> m;
nr = max(nl, nr);
while(m--) {
int u, v;
long long w;
cin >> u >> v >> w;
W[u][v] = w;
lx[u] = max(lx[u], w);
}
for (int i=1; i<=nl; i++) {
for (int x=1; x<=nl; x++) vx[x] = 0;
for (int y=1; y<=nr; y++) vy[y] = 0, slack[y] = INF64; match(i);
}
long long ans = 0;
for (int i=1; i<=nl; i++) ans += W[i][mx[i]];
cout << ans << '\n';
for (int i=1; i<=nl; i++) {
if (i > 1) cout << ' ';
cout << (W[i][mx[i]] ? mx[i] : 0);
}
cout << '\n';
}
```
### Matching.txt
最 大 匹 配 + 最 小 邊 覆 蓋 = V
最 大 獨 立 集 + 最 小 點 覆 蓋 = V
最 大 匹 配 = 最 小 點 覆 蓋
最 小 路 徑 覆 蓋 數 = V - 最 大 匹 配 數
### Maximum General Matching
```C++=
// Maximum Cardinality Matching
struct Graph {
vector<int> G[MAXN];
int pa[MAXN], match[MAXN], st[MAXN], S[MAXN], vis[
MAXN];
int t, n;
void init(int _n) {
n = _n;
for ( int i = 1 ; i <= n ; i++ ) G[i].clear();
}
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
int lca(int u, int v){
for ( ++t ; ; swap(u, v) ) {
if ( u == 0 ) continue;
if ( vis[u] == t ) return u;
vis[u] = t;
u = st[ pa[ match[u] ] ];
}
}
void flower(int u, int v, int l, queue<int> &q) {
while ( st[u] != l ) {
pa[u] = v;
if ( S[ v = match[u] ] == 1 ) {
q.push(v);
S[v] = 0;
}
st[u] = st[v] = l;
u = pa[v];
}
}
bool bfs(int u){
for ( int i = 1 ; i <= n ; i++ ) st[i] = i;
memset(S, -1, sizeof(S));
queue<int>q;
q.push(u);
S[u] = 0;
while ( !q.empty() ) {
u = q.front(); q.pop();
for ( int i = 0 ; i < (int)G[u].size(); i++) {
int v = G[u][i];
if ( S[v] == -1 ) {
pa[v] = u;
S[v] = 1;
if ( !match[v] ) {
for ( int lst ; u ; v = lst, u = pa[v] ) {
lst = match[u];
match[u] = v;
match[v] = u;
}
return 1;
}
q.push(match[v]);
S[ match[v] ] = 0;
} else if ( !S[v] && st[v] != st[u] ) {
int l = lca(st[v], st[u]);
flower(v, u, l, q);
flower(u, v, l, q);
}
}
}
return 0;
}
int solve(){
memset(pa, 0, sizeof(pa));
memset(match, 0, sizeof(match));
int ans = 0;
for ( int i = 1 ; i <= n ; i++ )
if ( !match[i] && bfs(i) ) ans++;
return ans;
}
} graph;
```
### Minimum General Weighted Matching
```C++=
// Minimum Weight Perfect Matching (Perfect Match)
struct Graph {
static const int MAXN = 105;
int n, e[MAXN][MAXN];
int match[MAXN], d[MAXN], onstk[MAXN];
vector<int> stk;
void init(int _n) {
n = _n;
for( int i = 0 ; i < n ; i ++ )
for( int j = 0 ; j < n ; j ++ )
e[i][j] = 0;
}
void add_edge(int u, int v, int w) {
e[u][v] = e[v][u] = w;
}
bool SPFA(int u){
if (onstk[u]) return true;
stk.push_back(u);
onstk[u] = 1;
for ( int v = 0 ; v < n ; v++ ) {
if (u != v && match[u] != v && !onstk[v] )
{
int m = match[v];
if ( d[m] > d[u] - e[v][m] + e[u][v] )
{
d[m] = d[u] - e[v][m] + e[u][v];
onstk[v] = 1;
stk.push_back(v);
if (SPFA(m)) return true;
stk.pop_back();
onstk[v] = 0;
}
}
}
onstk[u] = 0;
stk.pop_back();
return false;
}
int solve() {
for ( int i = 0 ; i < n ; i += 2 ) {
match[i] = i+1;
match[i+1] = i;
}
while (true){
int found = 0;
for ( int i = 0 ; i < n ; i++ )
onstk[ i ] = d[ i ] = 0;
for ( int i = 0 ; i < n ; i++ ) {
stk.clear();
if ( !onstk[i] && SPFA(i) ) {
found = 1;
while ( stk.size() >= 2 ) {
int u = stk.back(); stk.
pop_back();
int v = stk.back(); stk.
pop_back();
match[u] = v;
match[v] = u;
}
}
}
if (!found) break;
}
int ret = 0;
for ( int i = 0 ; i < n ; i++ )
ret += e[i][match[i]];
ret /= 2;
return ret;
}
} graph;
```
## Graph
• Maximum Independent Set
– General: [NPC] maximum clique of complement of G
– Bipartite Graph: [P] Maximum Cardinality Bipartite Matching
– Tree: [P] dp
• Minimum Dominating Set
– General: [NPC]
– Bipartite Graph: [NPC]
– Tree: [P] DP
• Minimum Vertex Cover
– General: [NPC] (?)maximum clique of complement of G
– Bipartite Graph: [P] Maximum Cardinality Bipartite Matching
– Tree: [P] Greedy, from leaf to root
• Minimum Edge Cover
– General: [P] V - Maximum Matching
– Bipartite Graph: [P] Greedy, strategy: cover small degree node first.
– (Min/Max)Weighted: [P]: Minimum/Minimum Weight Matching
### BCC edge
邊 雙 連 通
任 意 兩 點 間 至 少 有 兩 條 不 重 疊 的 路 徑 連 接， 找 法：
1. 標 記 出 所 有 的 橋
2. 對 全 圖 進 行 DFS， 不 走 橋， 每 一 次 DFS 就 是 一 個 新 的 邊 雙 連 通
```C++=
// from BCW
struct BccEdge {
static const int MXN = 100005;
struct Edge { int v,eid; };
int n,m,step,par[MXN],dfn[MXN],low[MXN];
vector<Edge> E[MXN];
DisjointSet djs;
void init(int _n) {
n = _n; m = 0;
for (int i=0; i<n; i++) E[i].clear();
djs.init(n);
}
void add_edge(int u, int v) {
E[u].PB({v, m});
E[v].PB({u, m});
m++;
}
void DFS(int u, int f, int f_eid) {
par[u] = f;
dfn[u] = low[u] = step++;
for (auto it:E[u]) {
if (it.eid == f_eid) continue;
int v = it.v;
if (dfn[v] == -1) {
DFS(v, u, it.eid);
low[u] = min(low[u], low[v]);
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
void solve() {
step = 0;
memset(dfn, -1, sizeof(int)*n);
for (int i=0; i<n; i++) {
if (dfn[i] == -1) DFS(i, i, -1);
}
djs.init(n);
for (int i=0; i<n; i++) {
if (low[i] < dfn[i]) djs.uni(i, par[i]);
}
}
}graph;
```
### Dijkstra
```C++=
struct Edge{
int v; long long len;
bool operator < (const Edge &b)const { return len>b
.len; }
};
const long long INF = 1LL<<60;
void Dijkstra(int n, vector<Edge> G[], long long d[],
int s, int t=-1){
static priority_queue <Edge> pq;
while ( pq.size() )pq.pop();
for (int i=1; i<=n; i++)d[i]=INF;
d[s]=0; pq.push( {s,d[s]} );
while ( pq.size() ){
auto x = pq.top(); pq.pop();
int u = x.v;
if (d[u]<x.len)continue;
if (u==t)return;
for (auto &e:G[u]){
if (d[e.v] > d[u]+e.len){
d[e.v] = d[u]+e.len;
pq.push( {e.v,d[e.v]} );
}
}
}
}
```
### Domination.txt
#### Maximum Independent Set
General: [NPC] maximum clique of complement of G
Tree: [P] Greedy
Bipartite Graph: [P] Maximum Cardinality Bipartite Matching
#### Minimum Dominating Set
General: [NPC]
Tree: [P] DP
Bipartite Graph: [NPC]
#### Minimum Vertex Cover
General: [NPC] (?)maximum clique of complement of G
Tree: [P] Greedy, from leaf to root
Bipartite Graph: [P] Maximum Cardinality Bipartite Matching
#### Minimum Edge Cover
General: [P] V - Maximum Matching
Bipartite Graph: [P] Greedy, strategy: cover small degree node first.
(Min/Max)Weighted: [P]: Minimum/Minimum Weight Matching
### max clique
```C++=
const int MAXN = 105;
int best;
int n;
int num[MAXN];
int path[MAXN];
int G[MAXN][MAXN];
bool dfs( int *adj, int total, int cnt ){
int t[MAXN];
if (total == 0){
if( best < cnt ){
best = cnt;
return true;
}
return false;
}
for(int i = 0; i < total; i++){
if( cnt+(total-i) <= best ) return false;
if( cnt+num[adj[i]] <= best ) return false;
int k=0;
for(int j=i+1; j<total; j++)
if(G[ adj[i] ][ adj[j] ])
t[k++] = adj[j];
if (dfs(t, k, cnt+1)) return true;
}
return false;
}
int MaximumClique(){
int adj[MAXN];
if (n <= 0) return 0;
best = 0;
for(int i = n-1; i >= 0; i--){
int k=0;
for(int j = i+1; j < n; j++)
if (g[i][j]) adj[k++] = j;
dfs( adj, k, 1 );
num[i] = best;
}
return best;
}
```
### min mean cycle
```C++=
// from BCW
/* minimum mean cycle */
const int MAXE = 1805;
const int MAXN = 35;
const double inf = 1029384756;
const double eps = 1e-6;
struct Edge {
int v,u;
double c;
};
int n,m,prv[MAXN][MAXN], prve[MAXN][MAXN], vst[MAXN];
Edge e[MAXE];
vector<int> edgeID, cycle, rho;
double d[MAXN][MAXN];
inline void bellman_ford() {
for(int i=0; i<n; i++) d[0][i]=0;
for(int i=0; i<n; i++) {
fill(d[i+1], d[i+1]+n, inf);
for(int j=0; j<m; j++) {
int v = e[j].v, u = e[j].u;
if(d[i][v]<inf && d[i+1][u]>d[i][v]+e[j].c) {
d[i+1][u] = d[i][v]+e[j].c;
prv[i+1][u] = v;
prve[i+1][u] = j;
}
}
}
}
double karp_mmc() {
// returns inf if no cycle, mmc otherwise
double mmc=inf;
int st = -1;
bellman_ford();
for(int i=0; i<n; i++) {
double avg=-inf;
for(int k=0; k<n; k++) {
if(d[n][i]<inf-eps) avg=max(avg,(d[n][i]-d[k][i])
/(n-k));
else avg=max(avg,inf);
}
if (avg < mmc) tie(mmc, st) = tie(avg, i);
}
for(int i=0; i<n; i++) vst[i] = 0;
edgeID.clear(); cycle.clear(); rho.clear();
for (int i=n; !vst[st]; st=prv[i--][st]) {
vst[st]++;
edgeID.PB(prve[i][st]);
rho.PB(st);
}
while (vst[st] != 2) {
int v = rho.back(); rho.pop_back();
cycle.PB(v);
vst[v]++;
}
reverse(ALL(edgeID));
edgeID.resize(SZ(cycle));
return mmc;
}
```
### SSSP related concepts
最 短 路 問 題 分 類：
三 個 工 具 Bellman-Ford, Floyd, Dijkstra，
1. 可 以 把 Dijkstra Priority Queue 裡 面 存 的 東 西 想 成 「狀 態」， 他 可 以 拿 來 統 計 甚 至 轉 移。
2. 當 遇 到 邊 權 會 扣 掉 走 的 人 的 血 量 （或 油 量 之 類 的）， 當 不 能 有 負 值 的 時 候， 就 要 使 用 Bellman-Ford 來 做， 一 開 始 可 以 把 起 點 設 為 最 初 的 血 量 （油 量）， 拿 去 做 BellmanFord， 當 做 了 n-1 次 之 後， 還 能 轉 移， 那 就 是 有 負 環 或 正 環 （端 看 如 何 轉 移 Bellman-Ford， 這 部 分 的 轉 移 式 很 自 由 可 以 依 照 題 目 敘 述 亂 改。）
3. 特 別 注 意 如 果 要 判 到 某 一 個 點 的 ⻑ 度 是 不 是 無 限 小， 可 在 做 了 n-1 次 之 後， 發 現 u->v 可 以 更 新， 那 我 可 以 去 看 v 是 否 可 以 到 另 一 點 k， 如 果 是 聯 通 的， 代 表 k 這 個 點 的 ⻑ 度 是 無 限 小。
### Tarjan.cpp
#### 割 點
點 u 為 割 點 if and only if 滿 足 1. or 2.
1. u 爲 樹 根， 且 u 有 多 於 一 個 子 樹。
2. u 不 爲 樹 根， 且 滿 足 存 在 (u,v) 爲 樹 枝 邊 (或 稱 父 子 邊， 即 u 爲 v 在 搜 索 樹 中 的 父 親)， 使 得 DFN(u) <= Low(v) 。
-------------------------------------------------------
#### 橋
一 條 無 向 邊 (u,v) 是 橋 if and only if (u,v) 爲 樹 枝 邊， 且 滿 足 DFN(u) < Low(v)。
```C++=
// 0 base
struct TarjanSCC{
static const int MAXN = 1000006;
int n, dfn[MAXN], low[MAXN], scc[MAXN], scn, count;
vector<int> G[MAXN];
stack<int> stk;
bool ins[MAXN];
void tarjan(int u){
dfn[u] = low[u] = ++count;
stk.push(u);
ins[u] = true;
for(auto v:G[u]){
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u], low[v]);
}else if(ins[v]){
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u]){
int v;
do {
v = stk.top();
stk.pop();
scc[v] = scn;
ins[v] = false;
} while(v != u);
scn++;
}
}
void getSCC(){
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(ins,0,sizeof(ins));
memset(scc,0,sizeof(scc));
count = scn = 0;
for(int i = 0 ; i < n ; i++ ){
if(!dfn[i]) tarjan(i);
}
}
}SCC;
```
### 2-SAT
```C++=
const int MAXN = 2020;
struct TwoSAT{
static const int MAXv = 2*MAXN;
vector<int> GO[MAXv],BK[MAXv],stk;
bool vis[MAXv];
int SC[MAXv];
void imply(int u,int v){ // u imply v
GO[u].push_back(v);
BK[v].push_back(u);
}
int dfs(int u,vector<int>*G,int sc){
vis[u]=1, SC[u]=sc;
for (int v:G[u])if (!vis[v])
dfs(v,G,sc);
if (G==GO)stk.push_back(u);
}
int scc(int n=MAXv){
memset(vis,0,sizeof(vis));
for (int i=0; i<n; i++)if (!vis[i])
dfs(i,GO,-1);
memset(vis,0,sizeof(vis));
int sc=0;
while (!stk.empty()){
if (!vis[stk.back()])
dfs(stk.back(),BK,sc++);
stk.pop_back();
}
}
}SAT;
int main(){
SAT.scc(2*n);
bool ok=1;
for (int i=0; i<n; i++){
if (SAT.SC[2*i]==SAT.SC[2*i+1])ok=0;
}
if (ok){
for (int i=0; i<n; i++){
if (SAT.SC[2*i]>SAT.SC[2*i+1]){
cout << i << endl;
}
}
}
else puts("NO");
}
void warshall(){
bitset <2003> d[2003];
for (int k=0; k<n; k++){
for (int i=0; i<n; i++) if (d[i][k]) {
d[i] |= d[k];
}
}
}
```
### 平面圖判定
```C++=
//skydog
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <list>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <bitset>
#include <complex>
#include <climits>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> l4;
#define mp make_pair
#define pb push_back
#define debug(x) cerr << #x << " = " << x << " "
const int N=400+1;
struct Planar
{
int n,m,hash[N],fa[N],deep[N],low[N],ecp[N];
vector<int> g[N],son[N];
set< pair<int,int> > SDlist[N],proots[N];
int nxt[N][2],back[N],rev[N];
deque<int> q;
void dfs(int u)
{
hash[u]=1; q.pb(u);
ecp[u]=low[u]=deep[u];
int v;
for (int i = 0; i < g[u].size(); ++i)
if(!hash[v=g[u][i]])
{
fa[v]=u;
deep[v]=deep[u]+1;
dfs(v);
low[u]=min(low[u],low[v]);
SDlist[u].insert(mp(low[v],v));
}
else ecp[u]=min(ecp[u],deep[v]);
low[u]=min(low[u],ecp[u]);
}
int visited[N];
void addtree(int u,int t1,int v,int t2)
{
nxt[u][t1]=v; nxt[v][t2]=u;
}
void findnxt(int u,int v,int& u1,int& v1)
{
u1=nxt[u][v^1];
if(nxt[u1][0]==u) v1=0;
else v1=1;
}
void walkup(int u,int v)
{
back[v]=u;
int v1=v,v2=v,u1=1,u2=0,z;
for (;;)
{
if(hash[v1]==u || hash[v2]==u) break;
hash[v1]=u;hash[v2]=u; z=max(v1,v2);
if(z>n)
{
int p=fa[z-n];
if(p!=u)
{
proots[p].insert(mp(-low[z-n], z));
v1=p,v2=p,u1=0,u2=1;
}
else break;
}
else
{
findnxt(v1,u1,v1,u1);
findnxt(v2,u2,v2,u2);
}
}
}
int topstack;
pair<int,int> stack[N];
int outer(int u,int v)
{
return ecp[v]<deep[u] || (SDlist[v].size() &&
SDlist[v].begin()->first<deep[u]);
}
int inside(int u,int v)
{
return proots[v].size()>0 || back[v]==u;
}
int active(int u,int v)
{
return inside(u,v) || outer(u,v);
}
void push(int a,int b)
{
stack[++topstack]=mp(a,b);
}
void mergestack()
{
int v1,t1,v2,t2,s,s1;
v1=stack[topstack].first;t1=stack[topstack].
second;
topstack --;
v2=stack[topstack].first;t2=stack[topstack].
second;
topstack --;
s=nxt[v1][t1^1];
s1=(nxt[s][1]==v1);
nxt[s][s1]=v2;
nxt[v2][t2]=s;
SDlist[v2].erase( make_pair(low[v1-n],v1-n) );
proots[v2].erase( make_pair(-low[v1-n],v1) );
}
void findnxtActive(int u,int t,int& v,int& w1,int S
)
{
findnxt(u,t,v,w1);
while(u!=v && !active(S,v))
findnxt(v,w1,v,w1);
}
void walkdown(int S,int u)
{
topstack=0;
int t1,v=S,w1,x2,y2,x1,y1,p;
for(t1=0;t1<2;++t1)
{
findnxt(S,t1^1,v,w1);
while(v!=S)
{
if(back[v]==u)
{
while(topstack >0) mergestack();
addtree(S,t1,v,w1); back[v]=0;
}
if(proots[v].size())
{
push(v,w1);
p=proots[v].begin()->second;
findnxtActive(p,1,x1,y1,u);
findnxtActive(p,0,x2,y2,u);
if(active(u,x1) && !outer(u,x1))
v=x1,w1=y1;
else if(active(u,x2) && !outer(u,x2
))
v=x2,w1=y2;
else if(inside(u,x1) || back[x1]==u
)
v=x1,w1=y1;
else v=x2,w1=y2;
push(p,v==x2);
}
else if(v>n || ( ecp[v]>=deep[u] && !
outer(u,v) ))
findnxt(v,w1,v,w1);
else if(v<=n && outer(u,v) && !topstack
)
{
addtree(S,t1,v,w1); break;
}
else break;
}
}
}
int work(int u)
{
int v;
for (int i = 0; i < g[u].size(); ++i)
if(fa[v=g[u][i]]==u)
{
son[u].push_back(n+v);
proots[n+v].clear();
addtree(n+v,1,v,0);
addtree(n+v,0,v,1);
}
for (int i = 0; i < g[u].size(); ++i)
if(deep[v=g[u][i]]>deep[u]+1)
walkup(u,v);
topstack=0;
for (int i = 0; i < son[u].size(); ++i)
walkdown(son[u][i], u);
for (int i = 0; i < g[u].size(); ++i)
if(deep[v=g[u][i]]>deep[u]+1 && back[v])
return 0;
return 1;
}
void init(int _n)
{
n = _n;
m = 0;
for(int i=1;i<=2*n;++i)
{
g[i].clear();
SDlist[i].clear();
son[i].clear();
proots[i].clear();
nxt[i][0]=nxt[i][1]=0;
fa[i]=0;
hash[i]=0;low[i]=ecp[i]=deep[i]=back[i]=0;
q.clear();
}
}
void add(int u, int v)
{
++m;
g[u].pb(v); g[v].pb(u);
}
bool check_planar()
{
if(m>3*n-5)
return false;
// memset(hash,0,sizeof hash);
for(int i=1;i<=n;++i)
if(!hash[i])
{
deep[i]=1;
dfs(i);
}
memset(hash,0,sizeof hash);
//memset(hash, 0, (2*n+1)*sizeof(hash[0]));
// originally only looks at last n element
assert(q.size() == n);
while (!q.empty())
{
if (!work(q.back()))
return false;
q.pop_back();
}
return true;
}
} base, _new;
vector<ii> edges;
int n, m;
inline void build(int n, Planar &_new)
{
_new.init(n);
for (auto e : edges)
_new.add(e.first, e.second);
}
void end()
{
puts("-1");
exit(0);
}
bool vis[N];
const int maxp = 5;
int path[maxp], tp=0;
void dfs(int cur)
{
vis[cur] = true;
path[tp++] = cur;
if (tp == maxp)
{
auto it = lower_bound(base.g[cur].begin(), base.g[
cur].end(), path[0]);
if ( it != base.g[cur].end() && *it == path[0])
{
//a cycle
int x = n+1;
for (int i = 0; i < 5; ++i) edges.pb(mp(x,
path[i]));
build(x, _new);
if (_new.check_planar())
{
for (int i = 0; i < maxp; ++i) printf("
%d%c", path[i], i==maxp-1?'\n':' ')
;
exit(0);
}
for (int i = 0; i < 5; ++i) edges.pop_back
();
}
}
else
{
for (auto e : base.g[cur]) if (!vis[e]) dfs(e);
}
vis[cur] = false;
--tp;
}
int main()
{
scanf("%d %d", &n, &m);
if (n <= 4)
{
assert(false);
puts("0"); return 0;
}
for (int i = 0; i < m; ++i)
{
int u, v; scanf("%d %d", &u, &v);
edges.pb(mp(u, v));
}
build(n, base);
if (!base.check_planar()) end();
for (int i = 1; i <= n; ++i)
sort(base.g[i].begin(), base.g[i].end());
for (int i = 1; i <= n; ++i)
dfs(i);
end();
}
```
## Math
待新增
### ax+by=gcd(a,b)
```C++=
pair<int,int> extgcd(int a, int b){
if (b==0) return {1,0};
int k = a/b;
pair<int,int> p = extgcd(b,a-k*b);
return { p.second, p.first - k*p.second };
}
```
### FFT
```C++=
// use llround() to avoid EPS
typedef double Double;
const Double PI = acos(-1);
// STL complex may TLE
typedef complex<Double> Complex;
#define x real()
#define y imag()
template<typename Iter> // Complex*
void BitReverse(Iter a, int n){
for (int i=1, j=0; i<n; i++){
for (int k = n>>1; k>(j^=k); k>>=1);
if (i<j) swap(a[i],a[j]);
}
}
template<typename Iter> // Complex*
void FFT(Iter a, int n, int rev=1){ // rev = 1 or -1
assert( (n&(-n)) == n ); // n is power of 2
BitReverse(a,n);
Iter A = a;
for (int s=1; (1<<s)<=n; s++){
int m = (1<<s);
Complex wm( cos(2*PI*rev/m), sin(2*PI*rev/m) );
for (int k=0; k<n; k+=m){
Complex w(1,0);
for (int j=0; j<(m>>1); j++){
Complex t = w * A[k+j+(m>>1)];
Complex u = A[k+j];
A[k+j] = u+t;
A[k+j+(m>>1)] = u-t;
w = w*wm;
}
}
}
if (rev==-1){
for (int i=0; i<n; i++){
A[i] /= n;
}
}
}
```
### NTT
```C++=
// Remember coefficient are mod P
// {n, 2^n, p, a, root} Note: p = a*2^n+1
// {16, 65536, 65537, 1, 3}
// {20, 1048576, 7340033, 7, 3}
template < LL P, LL root, int MAXN > // (must be 2^k)
struct NTT {
static LL bigmod(LL a, LL b) {
LL res = 1;
for (LL bs = a; b; b >>= 1, bs = (bs * bs) % P)
if (b & 1) res = (res * bs) % P;
return res;
}
static LL inv(LL a, LL b) {
if (a == 1) return 1;
return (((LL)(a - inv(b % a, a)) * b + 1) / a)
% b;
}
LL omega[MAXN + 1];
NTT() {
omega[0] = 1;
LL r = bigmod(root, (P - 1) / MAXN);
for (int i = 1; i <= MAXN; i++)
omega[i] = (omega[i - 1] * r) % P;
}
// n must be 2^k
void tran(int n, LL a[], bool inv_ntt = false) {
int basic = MAXN / n, theta = basic;
for (int m = n; m >= 2; m >>= 1) {
int mh = m >> 1;
for (int i = 0; i < mh; i++) {
LL w = omega[i * theta % MAXN];
for (int j = i; j < n; j += m) {
int k = j + mh;
LL x = a[j] - a[k];
if (x < 0) x += P;
a[j] += a[k];
if (a[j] > P) a[j] -= P;
a[k] = (w * x) % P;
}
}
theta = (theta * 2) % MAXN;
}
int i = 0;
for (int j = 1; j < n - 1; j++) {
for (int k = n >> 1; k > (i ^= k); k >>= 1)
;
if (j < i) swap(a[i], a[j]);
}
if (inv_ntt) {
LL ni = inv(n, P);
reverse(a + 1, a + n);
for (i = 0; i < n; i++)
a[i] = (a[i] * ni) % P;
}
}
};
const LL P=2013265921, root=31;
const int MAXN=4194304; // MAXN 的 因 數 也 可 以 跑
NTT<P, root, MAXN> ntt;
```
### GaussElimination
```C++=
// by bcw_codebook
const int MAXN = 300;
const double EPS = 1e-8;
int n;
double A[MAXN][MAXN];
void Gauss() {
for(int i = 0; i < n; i++) {
bool ok = 0;
for(int j = i; j < n; j++) {
if(fabs(A[j][i]) > EPS) {
swap(A[j], A[i]);
ok = 1;
break;
}
}
if(!ok) continue;
double fs = A[i][i];
for(int j = i+1; j < n; j++) {
double r = A[j][i] / fs;
for(int k = i; k < n; k++) {
A[j][k] -= A[i][k] * r;
}
}
}
}
```
### inverse
```C++=
const int MAXN = 1000006;
int inv[MAXN];
void invTable(int bound, int p){
inv[1] = 1;
for (int i=2; i<bound; i++){
inv[i] = (long long)inv[p%i] * (p-p/i) %p;
}
}
int inv(int b, int p){
if (b==1) return 1;
return (long long)inv(p%b,p) * (p-p/b) %p;
}
```
### Miller-Rabin
```C++=
typedef long long LL;
inline LL bin_mul(LL a, LL n,const LL& MOD){
LL re=0;
while (n>0){
if (n&1) re += a;
a += a; if (a>=MOD) a-=MOD;
n>>=1;
}
return re%MOD;
}
inline LL bin_pow(LL a, LL n,const LL& MOD){
LL re=1;
while (n>0){
if (n&1) re = bin_mul(re,a,MOD);
a = bin_mul(a,a,MOD);
n>>=1;
}
return re;
}
bool is_prime(LL n){
//static LL sprp[3] = { 2LL, 7LL, 61LL};
static LL sprp[7] = { 2LL, 325LL, 9375LL,
28178LL, 450775LL, 9780504LL,
1795265022LL };
if (n==1 || (n&1)==0 ) return n==2;
int u=n-1, t=0;
while ( (u&1)==0 ) u>>=1, t++;
for (int i=0; i<3; i++){
LL x = bin_pow( sprp[i]%n, u, n);
if (x==0 || x==1 || x==n-1)continue;
for (int j=1; j<t; j++){
x=x*x%n;
if (x==1 || x==n-1)break;
}
if (x==n-1)continue;
return 0;
}
return 1;
}
```
### Mobius
```C++=
void mobius() {
fill(isPrime, isPrime + MAXN, 1);
mu[1] = 1, num = 0;
for (int i = 2; i < MAXN; ++i) {
if (isPrime[i]) primes[num++] = i, mu[i] = -1;
static int d;
for (int j = 0; j < num && (d = i * primes[j])
< MAXN; ++j) {
isPrime[d] = false;
if (i % primes[j] == 0) {
mu[d] = 0; break;
} else mu[d] = -mu[i];
}
}
}
```
### pollardRho
```C++=
// from PEC
// does not work when n is prime
Int f(Int x, Int mod){
return add(mul(x, x, mod), 1, mod);
}
Int pollard_rho(Int n) {
if ( !(n & 1) ) return 2;
while (true) {
Int y = 2, x = rand()%(n-1) + 1, res = 1;
for ( int sz = 2 ; res == 1 ; sz *= 2 ) {
for ( int i = 0 ; i < sz && res <= 1 ; i++) {
x = f(x, n);
res = __gcd(abs(x-y), n);
}
y = x;
}
if ( res != 0 && res != n ) return res;
}
}
```
### SG
#### Anti Nim (取 走 最 後 一 個 石 子 者 敗)
先 手 必 勝 if and only if
1. 「所 有」 堆 的 石 子 數 都 為 1 且 遊 戲 的 SG 值 為 0。
2. 「有 些」 堆 的 石 子 數 大 於 1 且 遊 戲 的 SG 值 不 為 0。
-------------------------------------------------------
#### Anti-SG (決 策 集 合 為 空 的 遊 戲 者 贏)
定 義 SG 值 為 0 時， 遊 戲 結 束，
則 先 手 必 勝 if and only if
1. 遊 戲 中 沒 有 單 一 遊 戲 的 SG 函 數 大 於 1 且 遊 戲 的 SG 函 數 為 0。
2. 遊 戲 中 某 個 單 一 遊 戲 的 SG 函 數 大 於 1 且 遊 戲 的 SG 函 數 不 為 0。
-------------------------------------------------------
#### Sprague-Grundy
1. 雙 人、 回 合 制
2. 資 訊 完 全 公 開
3. 無 隨 機 因 素
4. 可 在 有 限 步 內 結 束
5. 沒 有 和 局
6. 雙 方 可 採 取 的 行 動 相 同
SG(S) 的 值 為 0： 後 手(P)必 勝
不 為 0： 先 手(N)必 勝
```C++=
int mex(set S) {
// find the min number >= 0 that not in the S
// e.g. S = {0, 1, 3, 4} mex(S) = 2
}
state = []
int SG(A) {
if (A not in state) {
S = sub_states(A)
if( len(S) > 1 ) state[A] = reduce(operator.xor, [
SG(B) for B in S])
else state[A] = mex(set(SG(B) for B in next_states(
A)))
}
return state[A]
}
```
### theorem
```C++=
/*
Lucas's Theorem
For non-negative integer n,m and prime P,
C(m,n) mod P = C(m/M,n/M) * C(m%M,n%M) mod P
= mult_i ( C(m_i,n_i) )
where m_i is the i-th digit of m in base P.
-------------------------------------------------------
Kirchhoff's theorem
A_{ii} = deg(i), A_{ij} = (i,j) \in E ? -1 : 0
Deleting any one row, one column, and cal the det(A)
-------------------------------------------------------
Nth Catalan recursive function:
C_0 = 1, C_{n+1} = C_n * 2(2n + 1)/(n+2)
-------------------------------------------------------
Mobius Formula
u(n) = 1 , if n = 1
(-1)^m , 若 n 無 平 方 數 因 數， 且 n = p1*p2*p3
*...*pk
0 , 若 n 有 大 於 1 的 平 方 數 因 數
- Property
1. (積 性 函 數) u(a)u(b) = u(ab)
2. ∑_{d|n} u(d) = [n == 1]
-------------------------------------------------------
Mobius Inversion Formula
if f(n) = ∑_{d|n} g(d)
then g(n) = ∑_{d|n} u(n/d)f(d)
= ∑_{d|n} u(d)f(n/d)
- Application
the number/power of gcd(i, j) = k
- Trick
分 塊, O(sqrt(n))
-------------------------------------------------------
Chinese Remainder Theorem (m_i 兩 兩 互 質)
x = a_1 (mod m_1)
x = a_2 (mod m_2)
....
x = a_i (mod m_i)
construct a solution:
Let M = m_1 * m_2 * m_3 * ... * m_n
Let M_i = M / m_i
t_i = 1 / M_i
t_i * M_i = 1 (mod m_i)
solution x = a_1 * t_1 * M_1 + a_2 * t_2 * M_2 + ...
+ a_n * t_n * M_n + k * M
= k*M + ∑ a_i * t_i * M_i, k is positive integer.
under mod M, there is one solution x = ∑ a_i * t_i *
M_i
-------------------------------------------------------
Burnside's lemma
|G| * |X/G| = sum( |X^g| ) where g in G
總 方 法 數: 每 一 種 旋 轉 下 不 動 點 的 個 數 總 和 除 以 旋 轉 的 方 法
數
*/
```
## Geometry
### 2D point template
```C++=
typedef double Double;
struct Point {
Double x,y;
bool operator < (const Point &b)const{
//return tie(x,y) < tie(b.x,b.y);
//return atan2(y,x) < atan2(b.y,b.x);
assert(0 && "choose compare");
}
Point operator + (const Point &b)const{
return {x+b.x,y+b.y};
}
Point operator - (const Point &b)const{
return {x-b.x,y-b.y};
}
Point operator * (const Double &d)const{
return {d*x,d*y};
}
Point operator / (const Double &d)const{
return {x/d,y/d};
}
Double operator * (const Point &b)const{
return x*b.x + y*b.y;
}
Double operator % (const Point &b)const{
return x*b.y - y*b.x;
}
friend Double abs2(const Point &p){
return p.x*p.x + p.y*p.y;
}
friend Double abs(const Point &p){
return sqrt( abs2(p) );
}
};
typedef Point Vector;
struct Line{
Point P; Vector v;
bool operator < (const Line &b)const{
return atan2(v.y,v.x) < atan2(b.v.y,b.v.x);
}
};
```
### circumcentre
```C++=
#include "2Dpoint.cpp"
Point circumcentre(Point &p0, Point &p1, Point &p2){
Point a = p1-p0;
Point b = p2-p0;
Double c1 = abs2(a)*0.5;
Double c2 = abs2(b)*0.5;
Double d = a % b;
Double x = p0.x + ( c1*b.y - c2*a.y ) / d;
Double y = p0.y + ( c2*a.x - c1*b.x ) / d;
return {x,y};
}
```
### ConvexHull
```C++=
#include "2Dpoint.cpp"
// retunr H, 第 一 個 點 會 在 H 出 現 兩 次
void ConvexHull(vector<Point> &P, vector<Point> &H){
int n = P.size(), m=0;
sort(P.begin(),P.end());
H.clear();
for (int i=0; i<n; i++){
while (m>=2 && (P[i]-H[m-2]) % (H[m-1]-H[m-2])
<0)H.pop_back(), m--;
H.push_back(P[i]), m++;
}
for (int i=n-2; i>=0; i--){
while (m>=2 && (P[i]-H[m-2]) % (H[m-1]-H[m-2])
<0)H.pop_back(), m--;
H.push_back(P[i]), m++;
}
}
```
### 3D ConvexHull
```C++=
// return the faces with pt indexes
int flag[MXN][MXN];
struct Point{
ld x,y,z;
Point operator - (const Point &b) const {
return (Point){x-b.x,y-b.y,z-b.z};
}
Point operator * (const ld &b) const {
return (Point){x*b,y*b,z*b};
}
ld len() const { return sqrtl(x*x+y*y+z*z); }
ld dot(const Point &a) const {
return x*a.x+y*a.y+z*a.z;
}
Point operator * (const Point &b) const {
return (Point){y*b.z-b.y*z,z*b.x-b.z*x,x*b.y-b.x*y
};
}
};
Point ver(Point a, Point b, Point c) {
return (b - a) * (c - a);
}
vector<Face> convex_hull_3D(const vector<Point> pt) {
int n = SZ(pt);
REP(i,n) REP(j,n)
flag[i][j] = 0;
vector<Face> now;
now.push_back((Face){0,1,2});
now.push_back((Face){2,1,0});
int ftop = 0;
for (int i=3; i<n; i++){
ftop++;
vector<Face> next;
REP(j, SZ(now)) {
Face& f=now[j];
ld d=(pt[i]-pt[f.a]).dot(ver(pt[f.a], pt[f.b], pt
[f.c]));
if (d <= 0) next.push_back(f);
int ff = 0;
if (d > 0) ff=ftop;
else if (d < 0) ff=-ftop;
flag[f.a][f.b] = flag[f.b][f.c] = flag[f.c][f.a]
= ff;
}
REP(j, SZ(now)) {
Face& f=now[j];
if (flag[f.a][f.b] > 0 and flag[f.a][f.b] != flag
[f.b][f.a])
next.push_back((Face){f.a,f.b,i});
if (flag[f.b][f.c] > 0 and flag[f.b][f.c] != flag
[f.c][f.b])
next.push_back((Face){f.b,f.c,i});
if (flag[f.c][f.a] > 0 and flag[f.c][f.a] != flag
[f.a][f.c])
next.push_back((Face){f.c,f.a,i});
}
now=next;
}
return now;
}
```
### half plane intersection
```C++=
bool OnLeft(const Line& L,const Point& p){
return Cross(L.v,p-L.P)>0;
}
Point GetIntersection(Line a,Line b){
Vector u = a.P-b.P;
Double t = Cross(b.v,u)/Cross(a.v,b.v);
return a.P + a.v*t;
}
int HalfplaneIntersection(Line* L,int n,Point* poly){
sort(L,L+n);
int first,last;
Point *p = new Point[n];
Line *q = new Line[n];
q[first=last=0] = L[0];
for(int i=1;i<n;i++){
while(first < last && !OnLeft(L[i],p[last-1])) last
--;
while(first < last && !OnLeft(L[i],p[first])) first
++;
q[++last]=L[i];
if(fabs(Cross(q[last].v,q[last-1].v))<EPS){
last--;
if(OnLeft(q[last],L[i].P)) q[last]=L[i];
}
if(first < last) p[last-1]=GetIntersection(q[last
-1],q[last]);
}
while(first<last && !OnLeft(q[first],p[last-1])) last
--;
if(last-first <=1) return 0;
p[last]=GetIntersection(q[last],q[first]);
int m=0;
for(int i=first;i<=last;i++) poly[m++]=p[i];
return m;
}
```
### Intersection of two circle
```C++=
vector<Point> interCircle(Point o1, Double r1, Point o2
, Double r2) {
Double d2 = abs2(o1 - o2);
Double d = sqrt(d2);
Point u = (o1+o2)*0.5 + (o1-o2)*(r2*r2-r1*r1)/(2.0*d2
);
if (abs((r1+r2)*(r1+r2) - d2) < 1e-6) return {u};
if (d < fabs(r1-r2) || r1+r2 < d) return {};
Double A = sqrt((r1+r2+d) * (r1-r2+d) * (r1+r2-d) *
(-r1+r2+d));
Point v = Point{o1.y-o2.y, -o1.x+o2.x} * A / (2.0*d2)
;
return {u+v, u-v};
}
```
### Intersection of two lines
```C++=
Point interPnt(Point p1, Point p2, Point q1, Point q2,
bool &res){
Double f1 = cross(p2, q1, p1);
Double f2 = -cross(p2, q2, p1);
Double f = (f1 + f2);
if(fabs(f) < EPS) {
res = false;
return {};
}
res = true;
return (f2 / f) * q1 + (f1 / f) * q2;
}
```
### Smallest Circle
```C++=
#include "circumcentre.cpp"
pair<Point,Double> SmallestCircle(int n, Point _p[]){
Point *p = new Point[n];
memcpy(p,_p,sizeof(Point)*n);
random_shuffle(p,p+n);
Double r2=0;
Point cen;
for (int i=0; i<n; i++){
if ( abs2(cen-p[i]) <= r2)continue;
cen = p[i], r2=0;
for (int j=0; j<i; j++){
if ( abs2(cen-p[j]) <= r2)continue;
cen = (p[i]+p[j])*0.5;
r2 = abs2(cen-p[i]);
for (int k=0; k<j; k++){
if ( abs2(cen-p[k]) <= r2)continue;
cen = circumcentre(p[i],p[j],p[k]);
r2 = abs2(cen-p[k]);
}
}
}
delete[] p;
return {cen,r2};
}
// auto res = SmallestCircle(,);
```
## String
### AC automaton
```C++=
// remember make_fail() !!!
// notice MLE
const int sigma = 62;
const int MAXC = 200005;
inline int idx(char c){
if ('A'<= c && c <= 'Z')return c-'A';
if ('a'<= c && c <= 'z')return c-'a' + 26;
if ('0'<= c && c <= '9')return c-'0' + 52;
assert(false);
}
struct ACautomaton{
struct Node{
Node *next[sigma], *fail;
int cnt; // dp
Node() : next{}, fail{}, cnt{}{}
} buf[MAXC], *bufp, *ori, *root;
void init(){
bufp = buf;
ori = new (bufp++) Node();
root = new (bufp++) Node();
}
void insert(char *s){
Node *ptr = root;
for (int i=0; s[i]; i++){
int c = idx(s[i]);
if (!ptr->next[c])
ptr->next[c] = new (bufp++) Node();
ptr = ptr->next[c];
}
ptr->cnt=1;
}
Node* trans(Node *o, int c){
while (!o->next[c]) o = o->fail;
return o->next[c];
}
void make_fail(){
static queue<Node*> que;
for (int i=0; i<sigma; i++)
ori->next[i] = root;
root->fail = ori;
que.push(root);
while ( que.size() ){
Node *u = que.front(); que.pop();
for (int i=0; i<sigma; i++){
if (!u->next[i])continue;
u->next[i]->fail = trans(u->fail,i);
que.push(u->next[i]);
}
u->cnt += u->fail->cnt;
}
}
} ac;
```
### KMP
```C++=
template<typename T>
void build_KMP(int n, T *s, int *f){ // 1 base
f[0]=-1, f[1]=0;
for (int i=2; i<=n; i++){
int w = f[i-1];
while (w>=0 && s[w+1]!=s[i])w = f[w];
f[i]=w+1;
}
}
template<typename T>
int KMP(int n, T *a, int m, T *b){
build_KMP(m,b,f);
int ans=0;
for (int i=1, w=0; i<=n; i++){
while ( w>=0 && b[w+1]!=a[i] )w = f[w];
w++;
if (w==m){
ans++;
w=f[w];
}
}
return ans;
}
```
### palindromic tree
```C++=
// remember init() !!!
// remember make_fail() !!!
// insert s need 1 base !!!
// notice MLE
const int sigma = 62;
const int MAXC = 1000006;
inline int idx(char c){
if ('a'<= c && c <= 'z')return c-'a';
if ('A'<= c && c <= 'Z')return c-'A'+26;
if ('0'<= c && c <= '9')return c-'0'+52;
}
struct PalindromicTree{
struct Node{
Node *next[sigma], *fail;
int len, cnt; // for dp
Node(){
memset(next,0,sizeof(next));
fail=0;
len = cnt = 0;
}
} buf[MAXC], *bufp, *even, *odd;
void init(){
bufp = buf;
even = new (bufp++) Node();
odd = new (bufp++) Node();
even->fail = odd;
odd->len = -1;
}
void insert(char *s){
Node* ptr = even;
for (int i=1; s[i]; i++){
ptr = extend(ptr,s+i);
}
}
Node* extend(Node *o, char *ptr){
int c = idx(*ptr);
while ( *ptr != *(ptr-1-o->len) )o=o->fail;
Node *&np = o->next[c];
if (!np){
np = new (bufp++) Node();
np->len = o->len+2;
Node *f = o->fail;
if (f){
while ( *ptr != *(ptr-1-f->len) )f=f->
fail;
np->fail = f->next[c];
}
else {
np->fail = even;
}
np->cnt = np->fail->cnt;
}
np->cnt++;
return np;
}
} PAM;
```
### SAM
```C++=
// par : fail link
// val : a topological order ( useful for DP )
// go[x] : automata edge ( x is integer in [0,26) )
struct SAM{
struct State{
int par, go[26], val;
State () : par(0), val(0){ FZ(go); }
State (int _val) : par(0), val(_val){ FZ(go); }
};
vector<State> vec;
int root, tail;
void init(int arr[], int len){
vec.resize(2);
vec[0] = vec[1] = State(0);
root = tail = 1;
for (int i=0; i<len; i++)
extend(arr[i]);
}
void extend(int w){
int p = tail, np = vec.size();
vec.PB(State(vec[p].val+1));
for ( ; p && vec[p].go[w]==0; p=vec[p].par)
vec[p].go[w] = np;
if (p == 0){
vec[np].par = root;
} else {
if (vec[vec[p].go[w]].val == vec[p].val+1){
vec[np].par = vec[p].go[w];
} else {
int q = vec[p].go[w], r = vec.size();
vec.PB(vec[q]);
vec[r].val = vec[p].val+1;
vec[q].par = vec[np].par = r;
for ( ; p && vec[p].go[w] == q; p=vec[p].par)
vec[p].go[w] = r;
}
}
tail = np;
}
};
```
### smallest rotation
```C++=
string mcp(string s){
int n = s.length();
s += s;
int i=0, j=1;
while (i<n && j<n){
int k = 0;
while (k < n && s[i+k] == s[j+k]) k++;
if (s[i+k] <= s[j+k]) j += k+1;
else i += k+1;
if (i == j) j++;
}
int ans = i < n ? i : j;
return s.substr(ans, n);
}
```
### suffix array
```C++=
/*he[i]保 存 了 在 後 綴 數 組 中 相 鄰 兩 個 後 綴 的 最 ⻑ 公 共 前 綴 ⻑ 度
*sa[i]表 示 的 是 字 典 序 排 名 為i的 後 綴 是 誰 （字 典 序 越 小 的 排
名 越 靠 前）
*rk[i]表 示 的 是 後 綴 我 所 對 應 的 排 名 是 多 少 */
const int MAX = 1020304;
int ct[MAX], he[MAX], rk[MAX];
int sa[MAX], tsa[MAX], tp[MAX][2];
void suffix_array(char *ip){
int len = strlen(ip);
int alp = 256;
memset(ct, 0, sizeof(ct));
for(int i=0;i<len;i++) ct[ip[i]+1]++;
for(int i=1;i<alp;i++) ct[i]+=ct[i-1];
for(int i=0;i<len;i++) rk[i]=ct[ip[i]];
for(int i=1;i<len;i*=2){
for(int j=0;j<len;j++){
if(j+i>=len) tp[j][1]=0;
else tp[j][1]=rk[j+i]+1;
tp[j][0]=rk[j];
}
memset(ct, 0, sizeof(ct));
for(int j=0;j<len;j++) ct[tp[j][1]+1]++;
for(int j=1;j<len+2;j++) ct[j]+=ct[j-1];
for(int j=0;j<len;j++) tsa[ct[tp[j][1]]++]=j;
memset(ct, 0, sizeof(ct));
for(int j=0;j<len;j++) ct[tp[j][0]+1]++;
for(int j=1;j<len+1;j++) ct[j]+=ct[j-1];
for(int j=0;j<len;j++)
sa[ct[tp[tsa[j]][0]]++]=tsa[j];
rk[sa[0]]=0;
for(int j=1;j<len;j++){
if( tp[sa[j]][0] == tp[sa[j-1]][0] &&
tp[sa[j]][1] == tp[sa[j-1]][1] )
rk[sa[j]] = rk[sa[j-1]];
else
rk[sa[j]] = j;
}
}
for(int i=0,h=0;i<len;i++){
if(rk[i]==0) h=0;
else{
int j=sa[rk[i]-1];
h=max(0,h-1);
for(;ip[i+h]==ip[j+h];h++);
}
he[rk[i]]=h;
}
}
```
### Z value
```C++=
z[0] = 0;
for ( int bst = 0, i = 1; i < len ; i++ ) {
if ( z[bst] + bst <= i ) z[i] = 0;
else z[i] = min(z[i - bst], z[bst] + bst - i);
while ( str[i + z[i]] == str[z[i]] ) z[i]++;
if ( i + z[i] > bst + z[bst] ) bst = i;
}
// 回 文 版
void Zpal(const char *s, int len, int *z) {
// Only odd palindrome len is considered
// z[i] means that the longest odd palindrom
centered at
// i is [i-z[i] .. i+z[i]]
z[0] = 0;
for (int b=0, i=1; i<len; i++) {
if (z[b]+b >= i) z[i] = min(z[2*b-i], b+z[b]-i)
;
else z[i] = 0;
while (i+z[i]+1 < len && i-z[i]-1 >= 0 &&
s[i+z[i]+1] == s[i-z[i]-1]) z[i] ++;
if (z[i]+i > z[b]+b) b = i;
}
}
```
### BWT (Burrows-Wheeler Transform)
```C++=
string BWT(string); // by suffix array
string iBWT(string &s, int start=0){
int n = (int) s.size();
string ret(n,' ');
vector<int> next(n,0), box[256];
for (int i=0; i<n; i++) // bucket sort
box[ (int)s[i] ].push_back(i);
for (int i=0, j=0; i<256; i++)
for (int x:box[i])
next[j++] = x;
for (int i=0, p=start; i<n; i++)
ret[i] = s[ p=next[p] ];
return ret;
}
```
## Data structure
### 2D range tree
```C++=
// remember sort x !!!!!
typedef int T;
const int LGN = 20;
const int MAXN = 100005;
struct Point{
T x, y;
friend bool operator < (Point a, Point b){
return tie(a.x,a.y) < tie(b.x,b.y);
}
};
struct TREE{
Point pt;
int toleft;
}tree[LGN][MAXN];
struct SEG{
T mx, Mx;
int sz;
TREE *st;
}seg[MAXN*4];
vector<Point> P;
void build(int l, int r, int o, int deep){
seg[o].mx = P[l].x;
seg[o].Mx = P[r].x;
seg[o].sz = r-l+1;;
if(l == r){
tree[deep][r].pt = P[r];
tree[deep][r].toleft = 0;
seg[o].st = &tree[deep][r];
return;
}
int mid = (l+r)>>1;
build(l,mid,o+o,deep+1);
build(mid+1,r,o+o+1,deep+1);
TREE *ptr = &tree[deep][l];
TREE *pl = &tree[deep+1][l], *nl = &tree[deep+1][
mid+1];
TREE *pr = &tree[deep+1][mid+1], *nr = &tree[deep
+1][r+1];
int cnt = 0;
while(pl != nl && pr != nr) {
*(ptr) = pl->pt.y <= pr->pt.y ? cnt++, *(pl++):
*(pr++);
ptr -> toleft = cnt; ptr++;
}
while(pl != nl) *(ptr) = *(pl++), ptr -> toleft =
++cnt, ptr++;
while(pr != nr) *(ptr) = *(pr++), ptr -> toleft =
cnt, ptr++;
}
int main(){
int n; cin >> n;
for(int i = 0 ;i < n; i++){
T x,y; cin >> x >> y;
P.push_back((Point){x,y});
}
sort(P.begin(),P.end());
build(0,n-1,1,0);
}
```
### ext heap
```C++=
#include <bits/extc++.h>
typedef __gnu_pbds::priority_queue <int> heap_t;
heap_t a,b;
int main() {
a.clear();
b.clear();
a.push(1);
a.push(3);
b.push(2);
b.push(4);
assert(a.top() == 3);
assert(b.top() == 4);
// merge two heap
a.join(b);
assert(a.top() == 4);
assert(b.empty());
return 0;
}
```
### KD tree
```C++=
// from BCW
const int MXN = 100005;
struct KDTree {
struct Node {
int x,y,x1,y1,x2,y2;
int id,f;
Node *L, *R;
}tree[MXN];
int n;
Node *root;
long long dis2(int x1, int y1, int x2, int y2) {
long long dx = x1-x2;
long long dy = y1-y2;
return dx*dx+dy*dy;
}
static bool cmpx(Node& a, Node& b){ return a.x<b.x; }
static bool cmpy(Node& a, Node& b){ return a.y<b.y; }
void init(vector<pair<int,int>> ip) {
n = ip.size();
for (int i=0; i<n; i++) {
tree[i].id = i;
tree[i].x = ip[i].first;
tree[i].y = ip[i].second;
}
root = build_tree(0, n-1, 0);
}
Node* build_tree(int L, int R, int dep) {
if (L>R) return nullptr;
int M = (L+R)/2;
tree[M].f = dep%2;
nth_element(tree+L, tree+M, tree+R+1, tree[M].f ?
cmpy : cmpx);
tree[M].x1 = tree[M].x2 = tree[M].x;
tree[M].y1 = tree[M].y2 = tree[M].y;
tree[M].L = build_tree(L, M-1, dep+1);
if (tree[M].L) {
tree[M].x1 = min(tree[M].x1, tree[M].L->x1);
tree[M].x2 = max(tree[M].x2, tree[M].L->x2);
tree[M].y1 = min(tree[M].y1, tree[M].L->y1);
tree[M].y2 = max(tree[M].y2, tree[M].L->y2);
}
tree[M].R = build_tree(M+1, R, dep+1);
if (tree[M].R) {
tree[M].x1 = min(tree[M].x1, tree[M].R->x1);
tree[M].x2 = max(tree[M].x2, tree[M].R->x2);
tree[M].y1 = min(tree[M].y1, tree[M].R->y1);
tree[M].y2 = max(tree[M].y2, tree[M].R->y2);
}
return tree+M;
}
int touch(Node* r, int x, int y, long long d2){
long long dis = sqrt(d2)+1;
if (x<r->x1-dis || x>r->x2+dis || y<r->y1-dis || y>
r->y2+dis)
return 0;
return 1;
}
void nearest(Node* r, int x, int y, int &mID, long
long &md2) {
if (!r || !touch(r, x, y, md2)) return;
long long d2 = dis2(r->x, r->y, x, y);
if (d2 < md2 || (d2 == md2 && mID < r->id)) {
mID = r->id;
md2 = d2;
}
// search order depends on split dim
if ((r->f == 0 && x < r->x) ||
(r->f == 1 && y < r->y)) {
nearest(r->L, x, y, mID, md2);
nearest(r->R, x, y, mID, md2);
} else {
nearest(r->R, x, y, mID, md2);
nearest(r->L, x, y, mID, md2);
}
}
int query(int x, int y) {
int id = 1029384756;
long long d2 = 102938475612345678LL;
nearest(root, x, y, id, d2);
return id;
}
}tree;
```
### Link-Cut tree
```C++=
// from bcw codebook
const int MXN = 100005;
const int MEM = 100005;
struct Splay {
static Splay nil, mem[MEM], *pmem;
Splay *ch[2], *f;
int val, rev, size;
Splay () : val(-1), rev(0), size(0) {
f = ch[0] = ch[1] = &nil;
}
Splay (int _val) : val(_val), rev(0), size(1) {
f = ch[0] = ch[1] = &nil;
}
bool isr() {
return f->ch[0] != this && f->ch[1] != this;
}
int dir() {
return f->ch[0] == this ? 0 : 1;
}
void setCh(Splay *c, int d) {
ch[d] = c;
if (c != &nil) c->f = this;
pull();
}
void push() {
if (rev) {
swap(ch[0], ch[1]);
if (ch[0] != &nil) ch[0]->rev ^= 1;
if (ch[1] != &nil) ch[1]->rev ^= 1;
rev=0;
}
}
void pull() {
size = ch[0]->size + ch[1]->size + 1;
if (ch[0] != &nil) ch[0]->f = this;
if (ch[1] != &nil) ch[1]->f = this;
}
} Splay::nil, Splay::mem[MEM], *Splay::pmem = Splay::
mem;
Splay *nil = &Splay::nil;
void rotate(Splay *x) {
Splay *p = x->f;
int d = x->dir();
if (!p->isr()) p->f->setCh(x, p->dir());
else x->f = p->f;
p->setCh(x->ch[!d], d);
x->setCh(p, !d);
p->pull(); x->pull();
}
vector<Splay*> splayVec;
void splay(Splay *x) {
splayVec.clear();
for (Splay *q=x;; q=q->f) {
splayVec.push_back(q);
if (q->isr()) break;
}
reverse(begin(splayVec), end(splayVec));
for (auto it : splayVec) it->push();
while (!x->isr()) {
if (x->f->isr()) rotate(x);
else if (x->dir()==x->f->dir()) rotate(x->f),rotate
(x);
else rotate(x),rotate(x);
}
}
Splay* access(Splay *x) {
Splay *q = nil;
for (;x!=nil;x=x->f) {
splay(x);
x->setCh(q, 1);
q = x;
}
return q;
}
void evert(Splay *x) {
access(x);
splay(x);
x->rev ^= 1;
x->push(); x->pull();
}
void link(Splay *x, Splay *y) {
// evert(x);
access(x);
splay(x);
evert(y);
x->setCh(y, 1);
}
void cut(Splay *x, Splay *y) {
// evert(x);
access(y);
splay(y);
y->push();
y->ch[0] = y->ch[0]->f = nil;
}
int N, Q;
Splay *vt[MXN];
int ask(Splay *x, Splay *y) {
access(x);
access(y);
splay(x);
int res = x->f->val;
if (res == -1) res=x->val;
return res;
}
int main(int argc, char** argv) {
scanf("%d%d", &N, &Q);
for (int i=1; i<=N; i++)
vt[i] = new (Splay::pmem++) Splay(i);
while (Q--) {
char cmd[105];
int u, v;
scanf("%s", cmd);
if (cmd[1] == 'i') {
scanf("%d%d", &u, &v);
link(vt[v], vt[u]);
} else if (cmd[0] == 'c') {
scanf("%d", &v);
cut(vt[1], vt[v]);
} else {
scanf("%d%d", &u, &v);
int res=ask(vt[u], vt[v]);
printf("%d\n", res);
}
}
return 0;
}
```
### Treap Lin
```C++=
#include <bits/stdc++.h>
using namespace std;
const int INF = 1<<30;
int ran(){
static unsigned x = 20190223;
return x = 0xdefaced*x+1;
}
struct Treap{
Treap *l,*r;
int num,m,sz,tag,ra,ad;
Treap(int a){
l=r=0; num=m=a; sz=1; tag=ad=0;
ra = ran();
}
};
int size(Treap *a){
return a ? a->sz : 0;
}
int min(Treap *a){
return a ? a->m+a->ad : INF;
}
void push(Treap *a){
if(!a) return;
if(a->tag){
swap(a->l,a->r);
if(a->l)a->l->tag ^= 1;
if(a->r)a->r->tag ^= 1;
a->tag=0;
}
if(a->l)a->l->ad += a->ad;
if(a->r)a->r->ad += a->ad;
a->num += a->ad;
a->m += a->ad;
a->ad = 0;
}
void pull(Treap *a){
if(!a) return;
a->sz=1+size(a->l)+size(a->r);
a->m = min({ a->num, min(a->l), min(a->r) });
}
Treap* merge(Treap *a, Treap *b){
if(!a || !b) return a ? a : b;
if(a->ra > b->ra){
push(a);
a->r = merge(a->r,b);
pull(a);
return a;
}else{
push(b);
b->l = merge(a,b->l);
pull(b);
return b;
}
}
void split (Treap *o, Treap *&a, Treap *&b, int k){
if(!k) a=0, b=o;
else if(size(o)==k) a=o, b=0;
else{
push(o);
if(k <= size(o->l)){
b = o;
split(o->l, a, b->l,k);
pull(b);
}else{
a = o;
split(o->r, a->r, b, k-size(o->l)-1);
pull(a);
}
}
}
int main(){
Treap *head=0, *ta, *tb, *tc, *td;
int a, b, c, n; scanf("%d",&n);
for(int i=0; i<n; i++){
int t; scanf("%d",&t);
head = merge(head,new Treap(t));
}
int Q; scanf("%d",&Q);
char ss[50];
while(Q--){
scanf("%s",ss);
if(strcmp(ss,"ADD")==0){
scanf("%d%d%d",&a,&b,&c);
split(head,tb,tc,b);
split(tb,ta,tb,a-1);
tb -> ad += c;
head = merge(ta, merge(tb, tc));
}else if(strcmp(ss,"REVERSE")==0){
scanf("%d%d",&a,&b);
split(head,tb,tc,b);
split(tb,ta,tb,a-1);
tb -> tag ^= 1;
head = merge(ta, merge(tb, tc));
}else if(strcmp(ss,"REVOLVE")==0){
scanf("%d%d%d",&a,&b,&c);
split(head,tb,tc,b);
split(tb,ta,tb,a-1);
int szz = size(tb);
c %= szz;
split(tb,tb,td,szz-c);
tb=merge(td,tb);
head = merge(ta, merge(tb, tc));
}else if(strcmp(ss,"INSERT")==0){
scanf("%d%d",&a,&b);
split(head,ta,tc,a);
tb = new Treap(b);
head = merge(ta, merge(tb, tc));
}else if(strcmp(ss,"DELETE")==0){
scanf("%d",&a);
split(head,ta,tc,a-1);
split(tc,tb,tc,1);
delete tb;
head = merge(ta,tc);
}else if(strcmp(ss,"MIN")==0){
scanf("%d%d",&a,&b);
split(head,tb,tc,b);
split(tb,ta,tb,a-1);
printf("%d\n",min(tb));
head = merge(ta, merge(tb, tc));
}
}
}
```
## Other
### count spanning tree
#### 新 的 方 法 介 绍
下 面 我 们 介 绍 一 种 新 的 方 法 — — Matrix-Tree定 理(Kirchhoff矩阵-树 定 理)。
Matrix-Tree定 理 是 解 决 生 成 树 计 数 问 题 最 有 力 的 武 器 之 一。 它 首 先 于1847年 被Kirchhoff证 明。 在 介 绍 定 理 之 前， 我 们 首 先 明 确 几 个 概 念：
1、G的 度 数 矩 阵D[G]是 一 个n*n的 矩 阵， 并 且 满 足： 当i≠j时, dij=0； 当i=j时， dij等 于vi的 度 数。
2、G的 邻 接 矩 阵A[G]也 是 一 个n*n的 矩 阵， 并 且 满 足： 如 果vi、vj之 间 有 边 直 接 相 连， 则aij=1， 否 则 为0。
我 们 定 义G的Kirchhoff矩 阵(也 称 为 拉 普 拉 斯 算 子)C[G]为C[G]= D[G]-A[G]，则Matrix-Tree定 理 可 以 描 述 为：G的 所 有 不 同 的 生 成 树 的 个 数 等 于 其Kirchhoff矩 阵C[G]任 何 一 个n-1阶 主 子 式 的 行 列 式 的 绝 对 值。 所 谓n-1阶 主 子 式， 就 是 对 于r(1≤r≤n)， 将C[G]的 第r行、 第r列 同 时 去 掉 后 得 到 的 新 矩 阵， 用Cr[G]表 示。
#### 生 成 树 计 数
算 法 步 骤：
1、 构 建 拉 普 拉 斯 矩 阵
Matrix[i][j] =
degree(i) , i==j
-1，i-j有 边
0， 其 他 情 况
2、 去 掉 第r行， 第r列 （r任 意）
3、 计 算 矩 阵 的 行 列 式
```C++=
/* ***********************************************
MYID : Chen Fan
LANG : G++
PROG : Count_Spaning_Tree_From_Kuangbin
************************************************ */
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;
const double eps = 1e-8;
const int MAXN = 110;
int sgn(double x)
{
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
double b[MAXN][MAXN];
double det(double a[][MAXN],int n)
{
int i, j, k, sign = 0;
double ret = 1;
for(i = 0;i < n;i++)
for(j = 0;j < n;j++) b[i][j] = a[i][j];
for(i = 0;i < n;i++)
{
if(sgn(b[i][i]) == 0)
{
for(j = i + 1; j < n;j++)
if(sgn(b[j][i]) != 0) break;
if(j == n)return 0;
for(k = i;k < n;k++) swap(b[i][k],b[j][k]);
sign++;
}
ret *= b[i][i];
for(k = i + 1;k < n;k++) b[i][k]/=b[i][i];
for(j = i+1;j < n;j++)
for(k = i+1;k < n;k++) b[j][k] -= b[j][i]*b[i][
k];
}
if(sign & 1)ret = -ret;
return ret;
}
double a[MAXN][MAXN];
int g[MAXN][MAXN];
int main()
{
int T;
int n,m;
int u,v;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(g,0,sizeof(g));
while(m--)
{
scanf("%d%d",&u,&v);
u--;v--;
g[u][v] = g[v][u] = 1;
}
memset(a,0,sizeof(a));
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
if(i != j && g[i][j])
{
a[i][i]++;
a[i][j] = -1;
}
double ans = det(a,n-1);
printf("%.0lf\n",ans);
}
return 0;
}
```
### C++11 random
```C++=
void init(){
std::random_device rd;
std::default_random_engine gen( rd() );
std::uniform_int_distribution <unsigned long long>
dis(0,ULLONG_MAX);
for (int i=0; i<MAXN; i++){
h[i] = dis(gen);
}
}
```
### Digit Counting
```C++=
int dfs(int pos, int state1, int state2 ....., bool
limit, bool zero) {
if ( pos == -1 ) return 是 否 符 合 條 件;
int &ret = dp[pos][state1][state2][....];
if ( ret != -1 && !limit ) return ret;
int ans = 0;
int upper = limit ? digit[pos] : 9;
for ( int i = 0 ; i <= upper ; i++ ) {
ans += dfs(pos - 1, new_state1, new_state2,
limit & ( i == upper), ( i == 0) && zero);
}
if ( !limit ) ret = ans;
return ans;
}
int solve(int n) {
int it = 0;
for ( ; n ; n /= 10 ) digit[it++] = n % 10;
return dfs(it - 1, 0, 0, 1, 1);
}
```
### DP optimization
#### Monotonicity & 1D/1D DP & 2D/1D DP
##### Definition xD/yD
1D/1D DP[j] = min(0≤i<j) { DP[i] + w(i, j) }; DP[0] = k
2D/1D DP[i][j] = min(i<k≤j) { DP[i][k - 1] + DP[k][j] }
+ w(i, j); DP[i][i] = 0
#### Monotonicity
c d
a | w(a, c) w(a, d)
b | w(b, c) w(b, d)
#### Monge Condition
Concave(凹 四 邊 形 不 等 式): w(a, c) + w(b, d) >= w(a, d) +
w(b, c)
Convex (凸 四 邊 形 不 等 式): w(a, c) + w(b, d) <= w(a, d) +
w(b, c)
Totally Monotone
Concave(凹 單 調): w(a, c) <= w(b, d) -----> w(a, d) <= w
(b, c)
Convex (凸 單 調): w(a, c) >= w(b, d) -----> w(a, d) >= w
(b, c)
#### 1D/1D DP O(n^2) -> O(nlgn)
*CONSIDER THE TRANSITION POINT*
Solve 1D/1D Concave by Stack
Solve 1D/1D Convex by Deque
#### 2D/1D Convex DP (Totally Monotone) O(n^3) -> O(n^2)
h(i, j − 1) ≤ h(i, j) ≤ h(i + 1, j)
### DP 1D/1D
```C++=
#include<bits/stdc++.h>
int t, n, L;
int p;
char s[MAXN][35];
ll sum[MAXN] = {0};
long double dp[MAXN] = {0};
int prevd[MAXN] = {0};
long double pw(long double a, int n) {
if ( n == 1 ) return a;
long double b = pw(a, n/2);
if ( n & 1 ) return b*b*a;
else return b*b;
}
long double f(int i, int j) {
// cout << (sum[i] - sum[j]+i-j-1-L) << endl;
return pw(abs(sum[i] - sum[j]+i-j-1-L), p) + dp[j];
}
struct INV {
int L, R, pos;
};
INV stk[MAXN*10];
int top = 1, bot = 1;
void update(int i) {
while ( top > bot && i < stk[top].L && f(stk[top].L
, i) < f(stk[top].L, stk[top].pos) ) {
stk[top - 1].R = stk[top].R;
top--;
}
int lo = stk[top].L, hi = stk[top].R, mid, pos =
stk[top].pos;
//if ( i >= lo ) lo = i + 1;
while ( lo != hi ) {
mid = lo + (hi - lo) / 2;
if ( f(mid, i) < f(mid, pos) ) hi = mid;
else lo = mid + 1;
}
if ( hi < stk[top].R ) {
stk[top + 1] = (INV) { hi, stk[top].R, i };
stk[top++].R = hi;
}
}
int main() {
cin >> t;
while ( t-- ) {
cin >> n >> L >> p;
dp[0] = sum[0] = 0;
for ( int i = 1 ; i <= n ; i++ ) {
cin >> s[i];
sum[i] = sum[i-1] + strlen(s[i]);
dp[i] = numeric_limits <long double>::max();
}
stk[top] = (INV) {1, n + 1, 0};
for ( int i = 1 ; i <= n ; i++ ) {
if ( i >= stk[bot].R ) bot++;
dp[i] = f(i, stk[bot].pos);
update(i);
// cout << (ll) f(i, stk[bot].pos) << endl;
}
if ( dp[n] > 1e18 ) {
cout << "Too hard to arrange" << endl;
} else {
vector<PI> as;
cout << (ll)dp[n] << endl;
}
}
return 0;
}
```
### Manhattan MST.cpp
```C++=
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int OFFSET = 2000; // y-x may < 0, offset it, if
y-x too large, please write a unique function
const int INF = 0xFFFFFFF;
int n;
int x[MAXN], y[MAXN], p[MAXN];
typedef pair<int, int> pii;
pii bit[MAXN]; // [ val, pos ]
struct P {
int x, y, id;
bool operator<(const P&b ) const {
if ( x == b.x ) return y > b.y;
else return x > b.x;
}
};
vector<P> op;
struct E {
int x, y, cost;
bool operator<(const E&b ) const {
return cost < b.cost;
}
};
vector<E> edges;
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
void update(int i, int v, int p) {
while ( i ) {
if ( bit[i].first > v ) bit[i] = {v, p};
i -= i & (-i);
}
}
pii query(int i) {
pii res = {INF, INF};
while ( i < MAXN ) {
if ( bit[i].first < res.first ) res = {bit[i].
first, bit[i].second};
i += i & (-i);
}
return res;
}
void input() {
cin >> n;
for ( int i = 0 ; i < n ; i++ ) cin >> x[i] >> y[i
], op.push_back((P) {x[i], y[i], i});
}
void mst() {
for ( int i = 0 ; i < MAXN ; i++ ) p[i] = i;
int res = 0;
sort(edges.begin(), edges.end());
for ( auto e : edges ) {
int x = find(e.x), y = find(e.y);
if ( x != y ) {
p[x] = y;
res += e.cost;
}
}
cout << res << endl;
}
void construct() {
sort(op.begin(), op.end());
for ( int i = 0 ; i < n ; i++ ) {
pii q = query(op[i].y - op[i].x + OFFSET);
update(op[i].y - op[i].x + OFFSET, op[i].x + op
[i].y, op[i].id);
if ( q.first == INF ) continue;
edges.push_back((E) {op[i].id, q.second, abs(x[
op[i].id]-x[q.second]) + abs(y[op[i].id]-y[
q.second]) });
}
}
void solve() {
// [45 ~ 90 deg]
for ( int i = 0 ; i < MAXN ; i++ ) bit[i] = {INF,
INF};
construct();
// [0 ~ 45 deg]
for ( int i = 0 ; i < MAXN ; i++ ) bit[i] = {INF,
INF};
for ( int i = 0 ; i < n ; i++ ) swap(op[i].x, op[i
].y);
construct();
for ( int i = 0 ; i < n ; i++ ) swap(op[i].x, op[i
].y);
// [-90 ~ -45 deg]
for ( int i = 0 ; i < MAXN ; i++ ) bit[i] = {INF,
INF};
for ( int i = 0 ; i < n ; i++ ) op[i].y *= -1;
construct();
// [-45 ~ 0 deg]
for ( int i = 0 ; i < MAXN ; i++ ) bit[i] = {INF,
INF};
for ( int i = 0 ; i < n ; i++ ) swap(op[i].x, op[i
].y);
construct();
// mst
mst();
}
int main () {
input();
solve();
return 0;
}
```
### stable marriage
```C++=
// normal stable marriage problem
// input:
//3
//Albert Laura Nancy Marcy
//Brad Marcy Nancy
//Chuck Laura Marcy Nancy
//Laura Chuck Albert Brad
//Marcy Albert Chuck Brad
//Nancy Brad Albert Chuck
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int n;
int favor[MAXN][MAXN]; // favor[boy_id][rank] = girl_id
;
int order[MAXN][MAXN]; // order[girl_id][boy_id] = rank
;
int current[MAXN]; // current[boy_id] = rank; boy_id
will pursue current[boy_id] girl.
int girl_current[MAXN]; // girl[girl_id] = boy_id;
void initialize() {
for ( int i = 0 ; i < n ; i++ ) {
current[i] = 0;
girl_current[i] = n;
order[i][n] = n;
}
}
map<string, int> male, female;
string bname[MAXN], gname[MAXN];
int fit = 0;
void stable_marriage() {
queue<int> que;
for ( int i = 0 ; i < n ; i++ ) que.push(i);
while ( !que.empty() ) {
int boy_id = que.front();
que.pop();
int girl_id = favor[boy_id][current[boy_id]];
current[boy_id] ++;
if ( order[girl_id][boy_id] < order[girl_id][
girl_current[girl_id]] ) {
if ( girl_current[girl_id] < n ) que.push(
girl_current[girl_id]); // if not the first
time
girl_current[girl_id] = boy_id;
} else {
que.push(boy_id);
}
}
}
int main() {
cin >> n;
for ( int i = 0 ; i < n; i++ ) {
string p, t;
cin >> p;
male[p] = i;
bname[i] = p;
for ( int j = 0 ; j < n ; j++ ) {
cin >> t;
if ( !female.count(t) ) {
gname[fit] = t;
female[t] = fit++;
}
favor[i][j] = female[t];
}
}
for ( int i = 0 ; i < n ; i++ ) {
string p, t;
cin >> p;
for ( int j = 0 ; j < n ; j++ ) {
cin >> t;
order[female[p]][male[t]] = j;
}
}
initialize();
stable_marriage();
for ( int i = 0 ; i < n ; i++ ) {
cout << bname[i] << " " << gname[favor[i][current[i
] - 1]] << endl;
}
}
```
### Mo’s algorithm
```C++=
int l = 0, r = 0, nowAns = 0, BLOCK_SIZE, n, m;
int ans[];
struct QUE{
int l, r, id;
friend bool operator < (QUE a, QUE b){
if(a.l / BLOCK_SIZE != b.l / BLOCK_SIZE)
return a.l / BLOCK_SIZE < b.l / BLOCK_SIZE;
return a.r < b.r;
}
}querys[];
inline void move(int pos, int sign) {
// update nowAns
}
void solve() {
BLOCK_SIZE = int(ceil(pow(n, 0.5)));
sort(querys, querys + m);
for (int i = 0; i < m; ++i) {
const QUE &q = querys[i];
while (l > q.l) move(--l, 1);
while (r < q.r) move(r++, 1);
while (l < q.l) move(l++, -1);
while (r > q.r) move(--r, -1);
ans[q.id] = nowAns;
}
}
```
### Parser
```C++=
using LL = long long;
const int MAXLEVEL = 2;
// binary operators
const vector<char> Ops[MAXLEVEL] = {
{'+', '-'}, // level 0
{'*', '/'} // level 1
};
// unary operators
const vector<pair<char,int>> Op1s = {
{'-', 0} // operator negative works on level 0
};
struct Node{
~Node(){ delete L; delete R; }
enum { op, op1, num } type;
LL val;
Node *L, *R;
} *root;
char getOp1(int LEVEL, istream& is){
is >>ws;
for (auto& x : Op1s){
auto& op = x.first;
auto& lev = x.second;
if (LEVEL == lev && is.peek() == op)
return is.get();
}
return 0;
}
template <int LEVEL> void parse(Node*& x, istream& is){
char op1 = getOp1(LEVEL, is);
parse<LEVEL+1>(x, is);
if (op1) x = new Node{Node::op1, op1, x, nullptr};
auto& ops = Ops[LEVEL];
while (is>>ws && count(ops.begin(), ops.end(), is.
peek())){
x = new Node{Node::op, is.get(), x, nullptr};
parse<LEVEL+1>(x->R, is);
}
}
template <> void parse<MAXLEVEL >(Node*& x, istream& is)
{
char op1 = getOp1(MAXLEVEL, is);
is>>ws;
if (is.peek()>='0' && is.peek()<='9'){
LL t; is >>t;
x = new Node{Node::num, t, nullptr, nullptr};
} else if (is.peek() == '('){
is.get();
parse<0>(x, is);
is>>ws;
if (is.get()!=')') throw 0;
} else throw 0;
if (op1) x = new Node{Node::op1, op1, x, nullptr};
}
// throw when error occur !!!!!
void build(istream& is){
parse<0>(root, is);
if ((is>>ws).peek() != EOF) throw 0;
}
```
### java cheat sheet
```C++=
import java.util.*;
import java.math.*;
import java.io.*;
public class java{
static class Comp implements Comparator<Integer >{
public int compare(Integer lhs, Integer rhs){
return lhs - rhs;
}
}
static class Yee implements Comparable<Yee>{
public int compareTo(Yee y){
return 0;
}
}
static class Reader{
private BufferedReader br;
private StringTokenizer st;
public Reader(){
br = new BufferedReader(new
InputStreamReader(System.in));
}
boolean hasNext() throws IOException{
String s;
while (st == null || !st.hasMoreElements())
{
if ((s = br.readLine())==null) return
false;
st = new StringTokenizer(s);
}
return true;
}
String next() throws IOException{
while (st == null || !st.hasMoreElements())
st = new StringTokenizer(br.readLine())
;
return st.nextToken();
}
int nextInt() throws IOException{
return Integer.parseInt(next());
}// Long.parseLong, Double.parseDouble, br.
readLine
}
public static void main(String args[])throws
IOException{
Reader cin = new Reader();
//Scanner cin = new Scanner(System.in);
PrintWriter cout = new PrintWriter(System.out);
//Scanner cin = new Scanner(new File("t.in"));
//PrintWriter cout = new PrintWriter(new File("
t.out"));
// ***** cout.close() or cout.flush() is needed
*****
// 2D array: int[][] a = new int[10][10];
// input, EOF, Graph
int n = cin.nextInt();
// nextFloat, nextLine, next
ArrayList<ArrayList<Integer>> G = new ArrayList
<>();
for (int i=0; i<n; i++) G.add(new ArrayList <>()
);
while (cin.hasNext()){ // EOF
int u = cin.nextInt(), v = cin.nextInt();
G.get(u).add(v);
}
// Math: E, PI, min, max, random(double 0~1),
sin...
// Collections(List a): swap(a,i,j), sort(a[,
comp]), min(a), binarySearch(a,val[,comp])
// set
Set<Integer> set = new TreeSet <>();
set.add(87); set.remove(87);
if (!set.contains(87)) cout.println("no 87");
// map
Map<String, Integer> map = new HashMap <>();
map.put("0", 1); map.put("2", 3);
for ( Map.Entry<String,Integer> i : map.
entrySet() )
cout.println(i.getKey() + " " + i.getValue
() + " wry");
cout.println( map.get("1") );
// Big Number: TEN ONE ZERO, modInverse
isProbablePrime modInverse modPow
// add subtract multiply divide remainder, and
or xor not shiftLeft shiftRight
// queue: add, peek(==null), poll
PriorityQueue <Integer> pq = new PriorityQueue <
Integer >(Collections.reverseOrder());
Queue<Integer> q = new ArrayDeque<Integer >();
// stack: push, empty, pop
Stack<Integer> s = new Stack<Integer >();
cout.close();
}
}
```
### python cheat sheet
```C++=
#!/usr/bin/env python3
# import
import math
from math import *
import math as M
from math import sqrt
# input
n = int( input() )
a = [ int(x) for x in input().split() ]
# EOF
while True:
try:
solve()
except:
break;
# output
print( x, sep=' ')
print( ''.join( str(x)+' ' for x in a ) )
print( '{:5d}'.format(x) )
# sort
a.sort()
sorted(a)
# list
a = [ x for x in range(n) ]
a.append(x)
# Basic operator
a, b = 10, 20
a/b # 0.5
a//b # 0
a%b # 10
a**b # 10^20
# if, else if, else
if a==0:
print('zero')
elif a>0:
print('postive')
else:
print('negative')
# loop
while a==b and b==c:
for i in LIST:
# stack # C++
stack = [3,4,5]
stack.append(6) # push()
stack.pop() # pop()
stack[-1] # top()
len(stack) # size() O(1)
# queue # C++
from collections import deque
queue = deque([3,4,5])
queue.append(6) # push()
queue.popleft() # pop()
queue[0] # front()
len(queue) # size() O(1)
# random
from random import *
randrange(L,R,step) # [L,R) L+k*step
randint(L,R) # int from [L,R]
choice(list) # pick 1 item from list
choices(list,k) # pick k item
shuffle(list)
Uniform(L,R) # float from [L,R]
# Decimal
from fractions import Fraction
from decimal import Decimal, getcontext
getcontext().prec = 250 # set precision
itwo = Decimal(0.5)
two = Decimal(2)
N = 200
def angle(cosT):
"""given cos(theta) in decimal return theta"""
for i in range(N):
cosT = ((cosT + 1) / two) ** itwo
sinT = (1 - cosT * cosT) ** itwo
return sinT * (2 ** N)
pi = angle(Decimal(-1))
# file IO
r = open("filename.in")
a = r.read() # read whole content into one string
w = open("filename.out", "w")
w.write('123\n')
# IO redirection
import sys
sys.stdin = open('filename.in')
sys.stdout = open('filename.out', 'w')
```
### Segment tree
```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){
cin >> total[x];
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){
//[ql, 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);
}
```
```C++=
const int N = 50010;
int n;
int w[N];
struct Node
{
int l, r;
int sum;
}tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)
{
if (l >= r) tr[u] = {l, r, w[r]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x) tr[u].sum += v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
else
{
int sum = 0;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) sum = query(u << 1, l, r);
if (r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
}
```
### Segment tree([Codeforce 339 problemD](https://codeforces.com/contest/339/problem/D))
```C++=
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int a[maxn],sum[maxn];
void pushup(int rt,int f) //樹的深度爲n+1 葉子結點不需要操作所以需要操作n次
{
if(f==1){
sum[rt] = sum[ls]|sum[rs];
// cout<<sum[ls]<<"和"<<sum[rs]<<"做or運算等於"<<sum[rt]<<"\n";
}
else{
sum[rt] = sum[ls]^sum[rs];
// cout<<sum[ls]<<"和"<<sum[rs]<<"做xor運算等於"<<sum[rt]<<"\n";
}
}
void build(int l,int r,int rt,int f)
{
if(l==r)
{
sum[rt] = a[l];
return ;
}
int m = (l+r)>>1;
build(l,m,ls,1-f);
build(m+1,r,rs,1-f);
pushup(rt,f);
}
void update(int p,int c,int l,int r,int rt,int f)
{
if(l==r)
{
sum[rt] = c;
return ;
}
int m = (l+r)>>1;
if(p<=m)
update(p,c,l,m,ls,1-f);
if(p>m)
update(p,c,m+1,r,rs,1-f);
pushup(rt,f);
}
int main()
{
int n,m;
int k;
scanf("%d%d",&n,&m);
k = (1<<n);
for(int i=1;i<=k;i++)
scanf("%d",&a[i]);
build(1,k,1,n%2); //保證從葉子節點開始的第一次操作爲 或 操作
for(int i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
update(x,y,1,k,1,n%2);
printf("%d\n",sum[1]);
}
return 0;
}
```
### Segment tree([d539: 區間 MAX](//https://zerojudge.tw/ShowProblem?problemid=d539))
```C++=
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define fastio ios::sync_with_stdio(false), cin.tie(NULL)
const int mxN = 5e5 + 5;
int n, st[mxN << 2];
void upd(int pos, int x, int v = 1, int l = 0, int r = n - 1) {
if(l == r) {
st[v] = x;
return;
}
int m = (l + r) >> 1;
if(pos <= m)
upd(pos, x, v << 1, l, m);
else
upd(pos, x, (v << 1) + 1, m + 1, r);
st[v] = max(st[v << 1], st[(v << 1) + 1]);
}
int qry(int l, int r, int v = 1, int L = 0, int R = n - 1) {
if(l == L && r == R)
return st[v];
int m = (L + R) >> 1;
if(r <= m)
return qry(l, r, v << 1, L, m);
else if(l > m)
return qry(l, r, (v << 1) + 1, m + 1, R);
return max(qry(l, m, v << 1, L, m), qry(m + 1, r, (v << 1) + 1, m + 1, R));
}
int main() {
fastio;
cin >> n;
for(int i = 0; i < n; ++i) {
int x;
cin >> x;
upd(i, x);
}
int q;
cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
--l, --r;
if(l > r)
swap(l, r);
cout << qry(l, r) << "\n";
}
return 0;
}
```
# Dynamic Programming
## LCS
### <font color="#f00">2個字串的LCS:</font>
1. 回傳LCS的長度
```C++=
int LCS(const string& A, const string& B) {
vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
for (int i{1}; i <= A.size(); ++i)
for (int j{1}; j <= B.size(); ++j) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
// 因為 A, B 是 0-indexed，透過 -1 調整
if (A[i - 1] == B[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
}
return dp[A.size()][B.size()];
}
```
2. 回傳LCS的字串
```C++=
string str_LCS(const string& A, const string& B) {
vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
for (int i{1}; i <= A.size(); ++i)
for (int j{1}; j <= B.size(); ++j) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
// 因為 A, B 是 0-indexed，透過 -1 調整
if (A[i - 1] == B[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
}
string ans{};
int i = A.size(), j=B.size();
while (dp[i][j]) {
if (dp[i][j] == dp[i - 1][j]) --i;
else if (dp[i][j] == dp[i][j - 1]) --j;
else ans += A[i - 1], --i, --j;
// cout << "i:"<<i<<"j:"<<j<<" "<<ans<<"\n";
}
return reverse(ans.begin(), ans.end()), ans;
}
```
### <font color="#f00">3個字串的LCS:</font>
1. 回傳LCS的長度
```C++=
int LCS(const string& A, const string& B,const string& C) {
vector<vector<vector<int>>> dp(A.size()+1,vector<vector<int>>(B.size()+1,vector<int>(C.size()+1,0)));
for (int i{1}; i <= A.size(); ++i)
for (int j{1}; j <= B.size(); ++j)
for (int k{1}; k <= C.size(); ++k){
if(i-2 >= 0) dp[i-2].clear(); //為了不浪費memory
dp[i][j][k]=max({dp[i-1][j][k],dp[i][j-1][k],dp[i][j][k-1]});
if (A[i - 1] == B[j - 1] && A[i - 1] ==C[k-1] && A[i-1]!='?'){
dp[i][j][k] = 1 + dp[i - 1][j - 1][k-1];
}
}
return dp[A.size()][B.size()][C.size()];
}
```
##### Articulation Points 的數量
:::spoiler
```C++=
/**
* Articulation Points 的數量
*
*/
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long ll;
vector< vector<int> > edge;
vector<int> dfn, low;
int result, dep;
void dfs(int cur, int par)
{
bool cut = false;
int child = 0;
dfn[cur] = low[cur] = ++dep;
for (auto& i : edge[cur]) {
if (!dfn[i]) {
++child;
dfs(i, cur);
low[cur] = min(low[cur], low[i]);
if (low[i] >= dfn[cur]) cut = true;
}
else if (i != par) low[cur] = min(low[cur], dfn[i]);
}
if ((child >= 2 || par != -1) && cut) ++result;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
while (cin >> N && N) {
cin.ignore();
result = 0, dep = 0;
edge.assign(N + 1, vector<int>());
dfn.assign(N + 1, 0);
low.assign(N + 1, 0);
string str;
while (getline(cin, str)) {
stringstream ss(str);
int u, v;
ss >> u;
if (!u) break;
while (ss >> v) edge[v].emplace_back(u), edge[u].emplace_back(v);
}
dfs(1, -1);
cout << result << "\n";
}
return 0;
}
```
:::
---
# Week 12 Graph
## <font color="#f00"> 橋（bridge）</font>和 <font color="#f00"> 關節點（AP, articulation point, cut vertex）</font>
```C++=
#include<vector>
#include<iostream>
using namespace std;
vector<int> vis(100,0);
vector<int> dfn(100,0);
vector<int> low(100,0);
vector<int> parent(100,-1);
vector<bool> ap(100);
vector<pair<int,int>> bridge(100);
vector<vector<int>> adj(100);
int d=0;
int cnt=0;
void dfs(int u)
{
//记录dfs遍历次序
static int counter = 0;
//记录节点u的子树数
int children = 0;
vis[u] = true;
//初始化dfn与low
dfn[u] = low[u] = ++counter;
for (int j = 0; j < adj[u].size(); j++)//遍历与u相连的顶点
{
int v = adj[u][j];
if (!vis[v])
{
children++;
parent[v] = u;//u是v的父节点
dfs(v);//深度优先搜索v
low[u] = min(low[u], low[v]);//等v完成深度优先搜索之后，low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点（即DFS次序号最小）
if (parent[u] == -1 && children > 1)//对根节点u，若其有两棵或两棵以上的子树，则该根结点u为割点；
{
//root如果大於2個child，就是articulation point
ap[u]=true;
}
if (parent[u] != -1 && low[v] >= dfn[u])//对非叶子节点u（非根节点），若其子树的节点均没有指向u的祖先节点的回边（条件low[v] >= dfn[u]表达的就是），说明删除u之后，根结点与u的子树的节点不再连通；则节点u为割点。
{
ap[u]=true;
}
if (low[v] >dfn[u]) //桥的条件
{
bridge.push_back(make_pair(u,v));
}
}else if (v != parent[u]) {//节点v已访问，则(u,v)为回边,且不是重边
low[u] = min(low[u], dfn[v]);
}
}
}
int main(){
int N=0;
while(cin>>N){
if(N==0) break;
int a;
while(cin >> a){
if(a==0) break;
int b;
while(cin>>b){
adj[a].push_back(b);
adj[b].push_back(a);
if(cin.get()=='\n') break ;
}
}
dfs(1);
for(int i=1;i<=N;i++){
if(ap[i]==1) cnt++;
}
cout<<"result:"<<cnt<<"\n";
}
}
```
:::
Computational_Geometry模板
:::spoiler
```C++=
struct Point{
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y){}
Point operator+(const Point &b)const{ // vector addition
return Point(x + b.x, y + b.y);
}
Point operator-(const Point &b)const{ // vector subtraction
return Point(x - b.x, y - b.y);
}
Point operator*(double d)const{ // scale (multiplication)
return Point(x * d, y * d);
}
Point operator/(double d)const{ // scale (division)
return Point(x / d, y / d);
}
double dot(const Point &b)const{ // vector dot
return x * b.x + y * b.y;
}
double cross(const Point &b)const{ // vector cross
return x * b.y - y * b.x;
}
};
// premise: three points are collinear
bool btw(const Point &p1, const Point &p2, const Point &p3){
return (p1 - p3).dot(p2 - p3) <= 0;
}
bool collinearity(const Point &p1, const Point &p2, const Point &p3){
return (p1 - p3).cross(p2 - p3) == 0;
}
bool pointOnSegment(const Point &p1, const Point &p2, const Point &p3){
return collinearity(p1, p2, p3) && btw(p1, p2, p3);
}
int ori(const Point &p1, const Point &p2, const Point &p3){
double d = (p2 - p1).cross(p3 - p1);
if(d == 0)
return 0;
return d > 0 ? 1 : -1;
}
bool seg_intersect(const Point &p1, const Point &p2, const Point &p3, const Point &p4){
int a123 = ori(p1, p2, p3);
int a124 = ori(p1, p2, p4);
int a341 = ori(p3, p4, p1);
int a342 = ori(p3, p4, p2);
if(a123 == 0 && a124 == 0)
return btw(p1, p2, p3) || btw(p1, p2, p4) || btw(p3, p4, p1) || btw(p3, p4, p2);
return a123 * a124 <= 0 && a341 * a342 <= 0;
}
Point intersect(const Point &p1, const Point &p2, const Point &p3, const Point &p4){
int a123 = (p2 - p1).cross(p3 - p1);
int a124 = (p2 - p1).cross(p4 - p1);
return (p4 * a123 - p3 * a124) / (a123 - a124);
}
```
:::
## Week 15
``` C++=
struct Point{
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y){}
Point operator+(const Point &b)const{ // 向量相加
return Point(x + b.x, y+b.y);
}
Point operator-(const Point &b)const{ // 向量相減
return Point(x - b.x, y- b.y);
}
Point operator*(double d)const{ // 伸長
return Point(x * d, y * d);
}
Point operator/(double d)const{ // 縮短
return Point(x / d, y / d);
}
double dot(const Point &b)const{ // 內積
return x * b.x + y * b.y;
}
double cross(const Point &b)const{ // 外積
return x * b.y - y * b.x;
}
bool btw(const Point &p1, const Point &p2, const Point &p3){ // 三點共線才能使用 -> 判斷點是否在線段內
return (p1 - p3).dot(p2 - p3) <= 0;
}
bool collinearity(const Point &p1, const Point &p2, const Point &p3){ // 判斷三點是否共線 -> 三角形之面積是否為 0
return (p1 - p3).cross(p2 - p3) == 0;
}
bool pointOnSegment(const Point &p1, const Point &p2, const Point &p3){ // 判斷 𝑃_3 是否在線段 (𝑃_1,𝑃_2) 中
return collinearity(p1, p2, p3) && btw(p1, p2, p3);
}
int ori(const Point &p1, const Point &p2, const Point &p3){ // 有向面積正負
double d = (p2 - p1).cross(p3 - p1);
if(d == 0)
return 0;
return d > 0 ? 1 : -1;
}
bool seg_intersect(const Point &p1, const Point &p2, const Point &p3, const Point &p4){ // 判斷線段相交
int a123 = ori(p1, p2, p3);
int a124 = ori(p1, p2, p4);
int a341 = ori(p3, p4, p1);
int a342 = ori(p3, p4, p2);
if(a123 == 0 && a124 == 0)
return btw(p1, p2, p3) || btw(p1, p2, p4) || btw(p3, p4, p1) || btw(p3, p4, p2);
return a123 * a124 <= 0 && a341 * a342 <= 0;
}
Point intersect(const Point &p1, const Point &p2, const Point &p3, const Point &p4){ // 找出直線交點
int a123 = (p2 - p1).cross(p3 - p1);
int a124 = (p2 - p1).cross(p4 - p1);
return (p4 * a123 - p3 * a124) / (a123 - a124);
}
bool cmp(const Point &a, const Point &b){
return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}
vector<Point> convexHull(vector<Point> v){ // 找出凸包
int sz = 0;
vector<Point> ans;
sort(v.begin(), v.end(), cmp);
for(size_t i = 0; i < v.size(); i++){
while(sz >= 2 && (ans[sz - 1] - ans[sz - 2]).cross(v[i]- ans[sz - 2]) <= 0)
ans.pop_back(), sz--;
ans.push_back(v[i]), sz++;
}
for(int i = int(v.size()) - 2, t = sz + 1; i >= 0; i--){
while(sz >= 2 && (ans[sz - 1] - ans[sz - 2]).cross(v[i]- ans[sz - 2]) <= 0)
ans.pop_back(), sz--;
ans.push_back(v[i]), sz++;
}
ans.pop_back();
return ans;
}
double rotatingCaliper(const vector<Point> &v){
double ans = 0;
for(int i = 0, j = 0; i < v.size(); i++){
while(abs2(v[i], v[j]) <= abs2(v[i], v[(j + 1) % v.size()]))
j = (j + 1) % v.size();
ans = abs2(v[i], v[j]);
}
return sqrt(ans);
}
}; struct Point{
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y){}
Point operator+(const Point &b)const{ // 向量相加
return Point(x + b.x, y+b.y);
}
Point operator-(const Point &b)const{ // 向量相減
return Point(x - b.x, y- b.y);
}
Point operator*(double d)const{ // 伸長
return Point(x * d, y * d);
}
Point operator/(double d)const{ // 縮短
return Point(x / d, y / d);
}
double dot(const Point &b)const{ // 內積
return x * b.x + y * b.y;
}
double cross(const Point &b)const{ // 外積
return x * b.y - y * b.x;
}
bool btw(const Point &p1, const Point &p2, const Point &p3){ // 三點共線才能使用 -> 判斷點是否在線段內
return (p1 - p3).dot(p2 - p3) <= 0;
}
bool collinearity(const Point &p1, const Point &p2, const Point &p3){ // 判斷三點是否共線 -> 三角形之面積是否為 0
return (p1 - p3).cross(p2 - p3) == 0;
}
bool pointOnSegment(const Point &p1, const Point &p2, const Point &p3){ // 判斷 𝑃_3 是否在線段 (𝑃_1,𝑃_2) 中
return collinearity(p1, p2, p3) && btw(p1, p2, p3);
}
int ori(const Point &p1, const Point &p2, const Point &p3){ // 有向面積正負
double d = (p2 - p1).cross(p3 - p1);
if(d == 0)
return 0;
return d > 0 ? 1 : -1;
}
bool seg_intersect(const Point &p1, const Point &p2, const Point &p3, const Point &p4){ // 判斷線段相交
int a123 = ori(p1, p2, p3);
int a124 = ori(p1, p2, p4);
int a341 = ori(p3, p4, p1);
int a342 = ori(p3, p4, p2);
if(a123 == 0 && a124 == 0)
return btw(p1, p2, p3) || btw(p1, p2, p4) || btw(p3, p4, p1) || btw(p3, p4, p2);
return a123 * a124 <= 0 && a341 * a342 <= 0;
}
Point intersect(const Point &p1, const Point &p2, const Point &p3, const Point &p4){ // 找出直線交點
int a123 = (p2 - p1).cross(p3 - p1);
int a124 = (p2 - p1).cross(p4 - p1);
return (p4 * a123 - p3 * a124) / (a123 - a124);
}
bool cmp(const Point &a, const Point &b){
return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}
vector<Point> convexHull(vector<Point> v){ // 找出凸包
int sz = 0;
vector<Point> ans;
sort(v.begin(), v.end(), cmp);
for(size_t i = 0; i < v.size(); i++){
while(sz >= 2 && (ans[sz - 1] - ans[sz - 2]).cross(v[i]- ans[sz - 2]) <= 0)
ans.pop_back(), sz--;
ans.push_back(v[i]), sz++;
}
for(int i = int(v.size()) - 2, t = sz + 1; i >= 0; i--){
while(sz >= 2 && (ans[sz - 1] - ans[sz - 2]).cross(v[i]- ans[sz - 2]) <= 0)
ans.pop_back(), sz--;
ans.push_back(v[i]), sz++;
}
ans.pop_back();
return ans;
}
double rotatingCaliper(const vector<Point> &v){
double ans = 0;
for(int i = 0, j = 0; i < v.size(); i++){
while(abs2(v[i], v[j]) <= abs2(v[i], v[(j + 1) % v.size()]))
j = (j + 1) % v.size();
ans = abs2(v[i], v[j]);
}
return sqrt(ans);
}
};
```
### X-Magic Pair (CF1612)
``` C++=
#include <bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define debug(x) cout<<"> "<< x<<endl;
#define ull unsigned long long
#define endl '\n'
#define lowbit(x) x&-x
//#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N =10 + 1e5 ,mod=1e9 + 7;
void solve()
{
ll a,b,x;
cin>>a>>b>>x;
bool ok =0;
while(a && b){
if(a>b)swap(a,b);
if(b >= x&& (x-b%a) % a == 0) ok = 1;
b %= a;
}
cout << (ok?"YES":"NO") << endl;
}
signed main()
{
ios::sync_with_stdio();cin.tie();cout.tie();
int T;cin>>T;
while(T--)
solve();
return 0;
}
```
### d271: 11582 - Colossal Fibonacci Numbers!
``` c++
#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
using namespace std;
typedef unsigned long long ULL;
const int UP = 1000 + 5;
int f[UP][UP*3], period[UP];
int qmod(ULL a, ULL b, ULL n) { // 快速冪模
a %= n;
ULL res = 1;
while(b) {
if(b & 1) res = res * a % n;
b >>= 1;
a = a * a % n;
}
return res;
}
int main() {
period[1] = 1;
for(int n = 2; n <= 1000; n++) {
f[n][0] = 0; f[n][1] = 1;
for(int i = 2; ; i++) {
f[n][i] = (f[n][i-1] + f[n][i-2]) % n;
if(f[n][i-1] == 0 && f[n][i] == 1) {
period[n] = i - 1;
break;
}
}
}
int T, n;
ULL a, b;
cin >> T;
while(T--) {
cin >>a>>b>>n;
int p = qmod(a, b, period[n]);
printf("%d\n", f[n][p]);
}
return 0;
}
```
### Problem for Nazar(CF1151)
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll quickmul(ll a,ll b)//b個a相乘，即a*b
{
ll ans=0;
while(b)
{
if(b&1)
ans=(ans+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return ans;
}
ll sum(ll x)
{
ll num=0,even=0,odd=0;
while(x>0)
{
if(num%2)
even+=min(x, (ll)1<<num);
else
odd+=min(x, (ll)1<<num);
x-=(ll)1<<num;
num++;
}
return (quickmul(odd,odd)+quickmul(even,even+1))%mod;
}
int main()
{
ll L,R;
cin>>L>>R;
cout<<(sum(R)-sum(L-1)+mod)%mod<<endl;
return 0;
}
```
### MaxFlow
``` C++=
// C++ program for implementation of Ford Fulkerson algorithm
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
// Number of vertices in given graph
#define V 6
/* Returns true if there is a path from source 's' to sink 't' in
residual graph. Also fills parent[] to store the path */
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
// Create a visited array and mark all vertices as not visited
bool visited[V];
memset(visited, 0, sizeof(visited));
// Create a queue, enqueue source vertex and mark source vertex as visited
queue<int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
// Standard BFS Loop
int u;
while (!q.empty())
{
// edge: u -> v
u = q.front(); // head point u
q.pop();
for (int v = 0; v < V; ++v) // tail point v
{
if (!visited[v] && rGraph[u][v] > 0) // find one linked vertex
{
q.push(v);
parent[v] = u; // find pre point
visited[v] = true;
}
}
}
// If we reached sink in BFS starting from source, then return true, else false
return visited[t] == true;
}
// Returns the maximum flow from s to t in the given graph
int fordFulkerson(int graph[V][V], int s, int t)
{
int u, v;
int rGraph[V][V];
for (u = 0; u < V; ++u)
{
for (v = 0; v < V; ++v)
{
rGraph[u][v] = graph[u][v];
}
}
int parent[V];
int max_flow = 0;
// Augment the flow while tere is path from source to sink
while (bfs(rGraph, s, t, parent))
{
// edge: u -> v
int path_flow = INT_MAX;
for (v = t; v != s; v = parent[v])
{
// find the minimum flow
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
// update residual capacities of the edges and reverse edges along the path
for (v = t; v != s; v = parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow; // assuming v->u weight is add path_flow
}
// Add path flow to overall flow
max_flow += path_flow;
}
return max_flow;
}
int main()
{
int graph[V][V] = { {0,16,13, 0, 0, 0},
{0, 0,10,12, 0, 0},
{0, 4, 0, 0,14, 0},
{0, 0, 9, 0, 0,20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
cout << "the maximum flow from v0 to v5 is:" << endl << fordFulkerson(graph, 0, 5);
return 0;
}
```
Sign in with Wallet
Connect another wallet