# CodeBook team21_34
## TIPS
### 萬用框架
``` C++
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// EOF
while (cin >> input) {
//pass
}
return 0;
}
```
---
### 資料型態
``` C++
Bytes Range
整數 int 4 -2*10^9 ~ 2*10^9 (2147483647)
short int 2 -32,768 ~ 32767
long long int 8 -9*10^18 ~ 9*10^18
單精數 float 4 ±3.4×10^-38 ~ ±3.4×10^38 (有效位數 7位)
倍精數 double 8 ±1.7×10^-308 ~ ±1.7×10^308 (有效位數 15位)
計算上 ±1e-14 才比大小
字元 char 1 0 ~ 255 (ASCII碼)
```
---
### MOD
``` C++
(a + b) mod n = [ (a mod n) + (b mod n) ] mod n
(a - b) mod n = [ (a mod n) - (b mod n) ] mod n
(a * b) mod n = [ (a mod n) * (b mod n) ] mod n
(a ^ b) mod n = [ (a mod n) ^ b ] mod n
(a / b) mod n = [ a * ((b mod n) mod^-1 n) ] mod n
```
``` C++
a ≡ b (mod n) & c ≡ d (mod n) <=> a+c ≡ b+d (mod n)
a ≡ b (mod n) & c ≡ d (mod n) <=> ac ≡ bd (mod n)
a ≡ b (mod n) <=> a^k ≡ b^k (mod n)
a ≡ b (mod n) <=> ak ≡ bk (mod n)
```
---
### 小數輸出
``` C++
streamsize ss = cout.precision();
cout << std::setprecision(5) << 12.3456789; // 12.345
cout << setprecision(5) << 12.3; // 12.3
cout << fixed << setprecision(5) << 12.3456789; // 12.34567
cout << fixed << setprecision(5) << 12.3; // 12.30000
cout << resetiosflags(ios::fixed | ios::showpoint) << setprecision(ss); // 重製
```
---
### 字元/字串
``` C++
// 讀取
cin.get(char);
cin.get(char*, num);
cin.getline(char*, num, 'delimiter');
// 在 cin >> 之後，要先讀一次垃圾
getline(cin, string, 'delimiter');
// 判斷
isalnum(char); // EN+NUM
isalpha(char); // EN
islower(char); // EN+NUM
isupper(char); // EN+NUM
isdigit(char); // NUM
// 大小寫轉換
transform(string.begin(), string.end(), dst_string.begin(), toupper/tolower);
// 型態轉換
string -> other : stoi(string) / stoll(string) / stof(string) / stod(string)
other -> string : string = to_string(other);
// 除去陣列裡面重複的字元
v.resize(unique(v.begin(), v.end())-v.begin());
```
---
### 字串分割
#### <string>.find
``` C++=1
#include <iostream>
#include <string>
using namespace std;
int main () {
string s = "scott>=tiger>=mushroom";
string delimiter = ">=";
size_t pos = 0;
string token;
while ((pos = s.find(delimiter)) != string::npos) {
token = s.substr(0, pos);
cout << token << endl;
s.erase(0, pos + delimiter.length());
}
cout << s << endl;
return 0;
}
```
#### <regex>
``` C++=1
#include <iostream>
#include <regex>
using namespace std;
int main () {
string input = "....";
regex rgx("\\s+");
sregex_token_iterator iter(input.begin(), input.end(), rgx, -1);
sregex_token_iterator end;
for (; iter != end; ++iter)
cout << *iter << '\n';
}
```
---
### <sstream>
``` C++
// 型態轉換
stringstream ss;
ss << type1;
ss >> type2;
// 與 getline 同時使用
stringstream ss;
getline(cin , str);
ss << str;
while (ss >> input) {}
// ss 重複使用
ss.clear();
```
#### string → int
``` C++
stringstream int2string;
int n = 12345;
int2string << n;
string s;
int2string >> s;
```
#### int → string
``` C++
stringstream string2int;
string s = "12345";
string2int << s;
int n;
string2int >> n;
```
---
### <algorithm>
``` C++
// data.begin() == arr
// data.end() == arr+n
// 排序
sort(data.begin(), data.end()); // increase
sort(data.begin(), data.end(), greater<>()); // decrease
sort(data.begin(), data.end(), cmp); // customize
// 二分搜，需sort，找 >= find 的位置
lower_bound(data.begin(), data.begin(), find);
// 二分搜，需sort，找 > find 的位置
upper_bound(data.begin(), data.begin(), find);
// 排列所有組合，需sort
do {} while (next_permutation(data.begin(), data.end()));
```
---
### <Containers>
|| vector | deque | stack | queue | set | map |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| in | push_back / insert | push_back / push_front / insert | push | push | insert | insert|
| access | front / back | front / back | top | front / back | find | operator[ ] / find |
| out | pop_back / erase | pop_back / pop_front / erase | pop | pop| erase | erase |
| size | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| empty | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| clear | ✓ | ✓ | ✗ | ✗ | ✓ | ✓ |
---
### 好用技巧
``` C++
// 2維動態陣列
// int** arr = new int[sizeX][sizeY]
int** aarrry = new int*[sizeX];
for (int i = 0; i < sizeX; ++i) {
arr[i] = new int[sizeY] (NMU);
}
vector<vector<int>> arr(sizeX, vector<int>(sizeY, NUM));
// 比大小
max({num1, num2, ...});
// priority queue
priority_queue<T, vector<T>, cmp> q;
```
#### 自定義比較
``` C++
// 可用在 algorithm.sort, priority_queue
struct compare{
bool operator()(const T& a, const T& b) {
// return a > b; // decrease
// return a < b; // increase
}
} cmp{};
```
#### Class operator overloading
``` C++=1
#include <iostream>
using namespace std;
class Complex {
int real;
int imaginary;
friend istream& operator >> (istream& in, Complex& op) {
in >> op.real >> op.imaginary;
return in;
}
friend ostream& operator << (ostream& out, const Complex& op) {
out << op.real << '+' << op.imaginary << "i";
return out;
}
public:
Complex operator + (const Complex& op2) const {
Complex res;
res.real = real + op2.real;
res.imaginary = imaginary + op2.imaginary;
return res;
}
// Can be used for algorithm sort()
bool operator < (const Complex& op2) const;
};
int main()
{
Complex c1, c2;
cin >> c1 >> c2; // 1 2 3 4
cout << c1 << ',' << c2 << '\n'; // 1+2i, 3+4i
cout << c1 + c2 << '\n'; // 4+6i
return 0;
}
```
---
## CODE
### 質數檢查
```c++=1
#include <iostream>
using namespace std;
int FastPower(long long x, int pow_num, int n) {
// x ^ pow_num % n
x %= n;
long long ans = 1;
for (; pow_num; pow_num >>= 1) {
if (pow_num & 1)
ans = ans * x % n;
x = x * x % n;
}
return ans;
}
bool solve(int num) {
if (num <= 4)
return num == 2 || num == 3;
int d = num - 1, digit = 0;
while (d % 2 == 0) digit++, d /= 2;
for (int a : {2, 7, 61}) {
if (num == a)
return true;
long long temp = FastPower(a, d, num);
if (temp == 1 || temp == num - 1)
continue;
for (int t = 0; t < digit; ++t) {
temp = temp * temp % num;
if (temp == 1)
return false;
if (temp == num - 1)
break;
}
if (temp != num - 1)
return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int x;
while (cin >> x) {
if (solve(x)) cout << "質數\n";
else cout << "非質數\n";
}
return 0;
}
```
### 找反mod數 (最小正整數)
```c++=1
#include <iostream>
using namespace std;
int gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = a < 0 ? -1 : 1;
y = 0; // 可以設為任意數
return x * a;
}
int g = gcd(b, a % b, y, x);
y -= a / b * x;
return g;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int a, n;
while (cin >> a >> n) {
if (n == 1) {
if (a == 1) cout << "1\n";
else cout << "No Inverse\n";
continue;
}
// ax + ny = 1 mod n
int x, y;
int ans = gcd(a, n, x, y);
if (ans == 1) {
while (x <= 0) x += n;
cout << x << '\n';
}
else cout << "No Inverse\n";
}
return 0;
}
```
### 費式數列 MOD
``` c++=1
#include <iostream>
#include <array>
using namespace std;
int pisano[1001] = { -1, 1 };
void Initialize() {
// f(x) mod n ≡ f(x mod n') mod n
// n' = pisano
int first, second, third, terms;
for (int i = 2; i <= 1000; ++i) {
first = terms = 0; second = 1;
do {
third = (first + second) % i;
first = second; second = third;
++terms;
} while (first != 0 || second != 1);
pisano[i] = terms;
}
}
unsigned long long FastPower(unsigned long long x, unsigned long long pow_num, int n) {
// x ^ pow_num % n
x %= n;
long long ans = 1;
for (; pow_num; pow_num >>= 1) {
if (pow_num & 1)
ans = ans * x % n;
x = x * x % n;
}
return ans;
}
unsigned long long FastPower(unsigned long long x, unsigned long long pow_num) {
// x ^ pow_num % n
long long ans = 1;
for (; pow_num; pow_num >>= 1) {
if (pow_num & 1)
ans = ans * x;
x = x * x;
}
return ans;
}
void mtx_mul(array<array<unsigned long long, 2>, 2> a,
array<array<unsigned long long, 2>, 2> b,
array<array<unsigned long long, 2>, 2>& res, int mod) {
for (int i{ 0 }; i < 2; ++i)
for (int j{ 0 }; j < 2; ++j) {
res[i][j] = 0;
for (int k{ 0 }; k < 2; ++k) {
res[i][j] += a[i][k] * b[k][j] % mod;
res[i][j] %= mod;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Initialize();
int t;
cin >> t;
while (t--) {
unsigned long long a, b, n, mod;
array<array<unsigned long long, 2>, 2> A{ 0, 1, 1, 1 }, ans{ 1, 0, 0, 1 };
cin >> a >> b >> mod;
if (pisano[mod] == 1) n = FastPower(a, b);
else n = FastPower(a, b, pisano[mod]);
for (; n; n >>= 1) {
if (n & 1)
mtx_mul(ans, A, ans, mod); // ans *= A
mtx_mul(A, A, A, mod); // A *= A
}
// | ans00 ans01 | ^ n = | x fn |
// | ans10 ans11 | | x x |
cout << ans[0][1] << '\n';
}
return 0;
}
```
### 幾何運算包
``` c++=1
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
class Point {
double x, y;
public:
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);
} // /
bool operator < (const Point& b) const {
return (x < b.x) || (x == b.x && y < b.y);
} // <
double dot (const Point& b) const {
// A 在 B 上的投影向量長度
// A 與 B 同向, 內積為正
// A 與 B 同向, 內積為負
// A 與 B 同向, 內積為零
return x * b.x + y * b.y;
} // vector dot
double cross (const Point& b) const {
// A 與 B 形成的平行四邊形面積
// A 到 B 順時針, 外積為負
// A 到 B 逆時針, 外積為正
return x * b.y - y * b.x;
} // vector cross
Point complex_mul (const Point& b) const {
// (a + bi) * (c + di) = (ac – bd) + (bc + ad)i
// = (k1 - k2) + (k1 + k3)i
// k1 = ac + bc = c (a + b)
// k2 = bc + bd = b (c + d)
// k3 = ad - ac = a (d - c)
double k1 = b.x * (x + y);
double k2 = y * (b.x + y);
double k3 = x * (y - b.x);
return Point(k1-k2, k1+k3);
}
double abs2(const Point& b) const {
return pow(x - b.x, 2) + pow(y - b.y, 2);
} // abs2
static bool point_in_segline_1D(const Point& start, const Point& end, const Point& p) {
// 必須要三點共線才能用
// start <- p -> end, dot <= 0
// p -> start -> end, dot > 0
// start -> end -> p, dot > 0
return (start - p).dot(end - p) <= 0;
} // point_in_segline_1D
static bool tripoint_in_sameline_2D(const Point& p1, const Point& p2, const Point& p3) {
// 三點構成面積 == 0, 共線
return (p1 - p3).cross(p2 - p3) == 0;
} // tripoint_in_sameline_2D
static bool point_in_segline_2D(const Point& start, const Point& end, const Point& p) {
// 共線 && 在線段中
return tripoint_in_sameline_2D(start, end, p) && point_in_segline_1D(start, end, p);
} // point_in_segline_2D
static int cross_n0p(const Point& ori, const Point& A, const Point& B) {
// 判斷正負或零
double d = (A - ori).cross(B - ori);
if (d == 0)
return 0;
return d > 0 ? 1 : -1;
} // cross_n0p
static bool seg_intersect(const Point& p1, const Point& p2, const Point& p3, const Point& p4) {
// P3 - P1
// | x |
// P2 - P4
int a123 = cross_n0p(p1, p2, p3);
int a124 = cross_n0p(p1, p2, p4);
int a341 = cross_n0p(p3, p4, p1);
int a342 = cross_n0p(p3, p4, p2);
// 共線
if (a123 == 0 && a124 == 0)
return point_in_segline_1D(p1, p2, p3) || point_in_segline_1D(p1, p2, p4) ||
point_in_segline_1D(p3, p4, p1) || point_in_segline_1D(p3, p4, p2);
// 不共線, <= 0 在不同側
return a123 * a124 <= 0 && a341 * a342 <= 0;
} // seg_intersect
static Point line_intersect_point(const Point& p1, const Point& p2, const Point& p3, const Point& p4) {
double a123 = (p2 - p1).cross(p3 - p1);
double a124 = (p2 - p1).cross(p4 - p1);
return (p4 * a123 - p3 * a124) / (a123 - a124);
} // line_intersect_point
static vector<Point> Graham(vector<Point>& data) {
sort(data.begin(), data.end());
int sz_b = 0;
vector<Point> ans_b;
for (int i = 0; i < data.size(); i++) {
while (sz_b >= 2 && (ans_b[sz_b-1]- ans_b[sz_b-2]).cross(data[i] - ans_b[sz_b-2]) <= 0) {
ans_b.pop_back(), sz_b--;
}
ans_b.push_back(data[i]), sz_b++;
}
int sz_t = 0;
vector<Point> ans_t;
for (int i = data.size()-1; i >= 0; i--) {
while (sz_t >= 2 && (ans_t[sz_t-1] - ans_t[sz_t-2]).cross(data[i] - ans_t[sz_t-2]) <= 0) {
ans_t.pop_back(), sz_t--;
}
ans_t.push_back(data[i]), sz_t++;
}
ans_b.insert(ans_b.end(), ans_t.begin()+1, ans_t.end());
return ans_b;
} // Graham
static double rotatingCaliper(const vector<Point>& data) {
double ans = 0;
for (int i = 0, j = 0; i < data.size(); i++) {
while ( data[i].abs2(data[j]) <= data[i].abs2(data[(j + 1) % data.size()]) )
j = (j + 1) % data.size();
ans = data[i].abs2(data[j]);
}
return sqrt(ans);
} // rotating
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Point p1(5, 6);
Point p2(3, 4);
cout << p1.dot(p2) << '\n'; // 39
cout << p1.cross(p2) << '\n'; // 2
vector<Point> data = { Point(5, 2), Point(4, 5), Point(2, 7), Point(2, 0), Point(1, 4) };
vector<Point> ans = Point::Graham(data);
vector<Point> data2 = { Point(1, 4) };
vector<Point> ans2 = Point::Graham(data2);
double ans3 = Point::rotatingCaliper(data);
return 0;
} // main
```
### 酷酷的線段樹和
``` c++=1
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 200 * 1000 + 13;
int n;
long long T;
int a[N];
int f[N];
void upd(int x){
for (int i = x; i < N; i |= i + 1)
++f[i];
}
int get(int x){
int res = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
res += f[i];
return res;
}
int main() {
scanf("%d%lld", &n, &T);
forn(i, n)
scanf("%d", &a[i]);
vector<long long> sums(1, 0ll);
long long pr = 0;
forn(i, n){
pr += a[i];
sums.push_back(pr);
}
sort(sums.begin(), sums.end());
sums.resize(unique(sums.begin(), sums.end()) - sums.begin());
long long ans = 0;
pr = 0;
upd(lower_bound(sums.begin(), sums.end(), 0ll) - sums.begin());
forn(i, n){
pr += a[i];
int npos = upper_bound(sums.begin(), sums.end(), pr - T) - sums.begin();
ans += (i + 1 - get(npos - 1));
int k = lower_bound(sums.begin(), sums.end(), pr) - sums.begin();
upd(k);
}
printf("%lld\n", ans);
return 0;
}
```
### SGT shiung0123 Template
```c++=1
template <class T>
class SGT {
int n;
vector<T> tree;
int root() { return 1; }
int left_child(int tree_index) { return 2 * tree_index; }
int right_child(int tree_index) { return 2 * tree_index + 1; }
unsigned power2ceil(unsigned n) {
// smallest power of 2 >= n
n -= 1;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n + 1;
} // power2ceil
T merge(const T &x, const T &y) {
return x + y;
} // merge
// [il, ir)
void build(const vector<T> &input, int il, int ir, int tree_index) {
if (ir - il == 1) tree[tree_index] = input[il];
else {
int im = (il + ir) / 2;
build(input, il, im, left_child(tree_index));
build(input, im, ir, right_child(tree_index));
tree[tree_index] =
merge(tree[left_child(tree_index)], tree[right_child(tree_index)]);
}
} // build
void modify(const int &target_index, const T &value, int il, int ir, int tree_index) {
if (ir - il == 1) tree[tree_index] = value;
else {
int im = (il + ir) / 2;
// left
if (target_index < im) modify(target_index, value, il, im, left_child(tree_index));
// right
else modify(target_index, value, im, ir, right_child(tree_index));
tree[tree_index] =
merge(tree[left_child(tree_index)], tree[right_child(tree_index)]);
}
} // set
T query(const int &target_l, const int &target_r, int il, int ir, int tree_index) {
if (target_l == il && target_r == ir) return tree[tree_index];
int im = (il + ir) / 2;
// left
if (target_r <= im) return query(target_l, target_r, il, im, left_child(tree_index));
// right
else if (target_l >= im) return query(target_l, target_r, im, ir, right_child(tree_index));
// cross
else return merge(
query(target_l, im, il, im, left_child(tree_index)),
query(im, target_r, im, ir, right_child(tree_index))
);
} // sum
public:
SGT(const vector<T>& input) {
n = input.size();
tree.resize(power2ceil(n)*2);
build(input, 0, n, root());
} // SGT
// target index start from 0
void modify(const int &target_index, const T &value) {
modify(target_index, value, 0, n, root());
} // set
// target index start from 0
T query(const int &target_l, const int &target_r) {
return query(target_l, target_r, 0, n, root());
} // sum
};
```
### Graph Template
```c++=1
// #pragma warning(disable:4996)
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <tuple>
#define INT_MAX 2147483647
using namespace std;
class cmp {
public:
bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
// return a < b; // decrease
return a.second > b.second; // increase
}
};
class Graph_adj {
private:
int v_num;
vector< list<pair<int, int>> > AdjList;
vector<int> color; // 0:未走訪, 1:走訪中, 2:走訪完畢
vector<int> distance;
vector<int> discover;
vector<int> finish;
vector<int> predecessor;
vector<int> size;
vector<int> dep;
vector<int> low;
vector<int> head;
vector<int> heavy;
vector<pair<int, int>> i2bi;
vector<vector<int>> bi2i;
void printData(const vector<int>& data, string str) {
cout << str << ":\n";
for (int i = 0; i < v_num; i++) {
cout << setw(4) << i;
}
cout << '\n';
for (int i = 0; i < v_num; i++) {
cout << setw(4) << data[i];
}
cout << '\n';
} // printData
void printData2D(const vector<vector<int>>& data, string str) {
cout << str << ":\n";
for (int i = 0; i < v_num; i++) {
for (int j = 0; j < v_num; j++) {
cout << data[i][j] << ' ';
}
cout << '\n';
}
cout << '\n';
} // printData
public:
Graph_adj() :v_num(0) {};
Graph_adj(int N) :v_num(N) {
AdjList.resize(v_num);
};
void AddEdgeList(int from, int to, int weight = 1, bool undirected = false) {
AdjList[from].push_back(make_pair(to, weight));
if (undirected) AdjList[to].push_back(make_pair(from, weight));
} // AddEdgeList
void ConnectedBFS(int Start) {
queue<int> q;
if (color[Start] == 0) {
color[Start] = 1; // 走訪中
distance[Start] = 0; // 起始點距離為0
predecessor[Start] = -1; // 起始點沒有父節點
q.push(Start);
while (!q.empty()) {
int cur = q.front();
for (auto& next : AdjList[cur]) {
if (color[next.first] == 0) {
color[next.first] = 1; // 走訪中
distance[next.first] = distance[cur] + 1; // 距離為cur+1
predecessor[next.first] = cur; // 父節點為cur
q.push(next.first);
}
}
color[cur] = 2; // 走訪完畢
q.pop();
} // while queue not empty
} // connected BFS end
} // ConnectedBFS
void BFS(int Start) {
color.resize(v_num, 0); // 走訪狀態
distance.resize(v_num, v_num + 1); // 與Start的距離
predecessor.resize(v_num, -1); // 紀錄父節點
ConnectedBFS(Start);
// 避免不連通的清況
for (int i = 0; i < v_num; i++) {
ConnectedBFS(i);
} // for all
printData(color, "color");
printData(distance, "distance");
printData(predecessor, "predecessor");
} // BFS
void ConnectedDFS(int cur, int& time) {
color[cur] = 1; // 走訪中
discover[cur] = ++time; // 紀錄發現時間
for (auto& next : AdjList[cur]) {
if (color[next.first] == 0) {
predecessor[next.first] = cur; // 父節點為cur
ConnectedDFS(next.first, time);
}
}
finish[cur] = ++time; // 紀錄完成時間
color[cur] = 2; // 走訪完畢
} // DFSVisit
void DFS(int Start) {
color.resize(v_num, 0); // 走訪狀態
discover.resize(v_num, 0); // 開始走訪時間
finish.resize(v_num, 0); // 完成走訪時間
predecessor.resize(v_num, -1); // 父節點
int time = 0;
if (color[Start] == 0)
ConnectedDFS(Start, time);
// 避免不連通的清況
for (int i = 0; i < v_num; i++) {
if (color[i] == 0)
ConnectedDFS(i, time);
} // for all
printData(color, "color");
printData(discover, "discover");
printData(finish, "finish");
printData(predecessor, "predecessor");
} // DFS
void DFS_order(vector<int> Start) {
color.resize(v_num, 0); // 走訪狀態
discover.resize(v_num, 0); // 開始走訪時間
finish.resize(v_num, 0); // 完成走訪時間
predecessor.resize(v_num, -1); // 父節點
int time = 0;
for (auto i : Start) {
if (color[i] == 0)
ConnectedDFS(i, time);
} // by order
// 避免不連通的清況
for (int i = 0; i < v_num; i++) {
if (color[i] == 0)
ConnectedDFS(i, time);
} // for all
printData(color, "color");
printData(discover, "discover");
printData(finish, "finish");
printData(predecessor, "predecessor");
} // DFS
int CollapsingFind(int cur) {
if (predecessor[cur] == -1) return cur;
else {
predecessor[cur] = CollapsingFind(predecessor[cur]);
return predecessor[cur];
}
} // CollapsingFind
void SetCollapsing() {
for (int i = 0; i < v_num; i++) {
CollapsingFind(i);
} // for all
int count = 0;
size.resize(v_num, 0);
for (int i = 0; i < v_num; i++) {
if (predecessor[i] == -1) count++, size[i]++;
else size[predecessor[i]]++;
}
cout << count << ' ' << *max_element(size.begin(), size.end()) << '\n';
} // SetCollapsing
Graph_adj GraphTranspose() {
Graph_adj gT(v_num);
for (int i = 0; i < v_num; i++) {
for (auto& next : AdjList[i]) {
gT.AddEdgeList(next.first, i);
}
} // for all
return gT;
} // GraphTranspose
vector<int> getDecreaseFinish() {
vector<pair<int, int>> temp;
temp.reserve(v_num);
for (int i = 0; i < v_num; i++) {
temp.push_back(make_pair(finish[i], i));
} // for all
sort(temp.begin(), temp.end(), greater<>());
vector<int> f;
f.reserve(v_num);
for (auto i : temp)
f.push_back(i.second);
printData(f, "finish order");
return f;
} // getDecreaseFinish
void MST_Prims(int Start) {
color.resize(v_num, 0); // 走訪狀態
distance.resize(v_num, INT_MAX); // 與Start的距離
predecessor.resize(v_num, -1); // 父節點
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
if (color[Start] == 0) {
color[Start] = 1; // 走訪中
distance[Start] = 0; // 起始點距離為0
predecessor[Start] = -1; // 起始點沒有父節點
q.push(make_pair(Start, 0));
while (!q.empty()) {
pair<int, int> cur = q.top();
q.pop();
if (color[cur.first] != 2) {
for (auto& next : AdjList[cur.first]) {
if (color[next.first] != 2 && next.second < distance[next.first]) {
color[next.first] = 1; // 走訪中
distance[next.first] = next.second; // 最短路徑為
predecessor[next.first] = cur.first; // 父節點為cur
q.push(make_pair(next.first, distance[next.first]));
}
}
color[cur.first] = 2; // 走訪完畢
} // not visited
} // while queue not empty
}
printData(color, "color");
printData(distance, "distance");
printData(predecessor, "predecessor");
/*
for (int i = 0; i < v_num; i++)
if (predecessor[i] != -1)
cout << predecessor[i] << '-' << distance[i] << '-' << i << '\n';
*/
} // MST_Prims
void SSSP_BF(int Start) {
distance.resize(v_num, INT_MAX); // 與Start的距離
predecessor.resize(v_num, -1); // 父節點
distance[Start] = 0; // 起始點距離為0
predecessor[Start] = -1; // 起始點沒有父節點
vector<bool> inqueue1(v_num, false), inqueue2(v_num, false);
queue<int> q1, q2; // 只處理有被relax的點，q1本輪更新，q2下輪更新
q1.push(Start);
inqueue1[Start] = true;
for (int i = 0; i < v_num; i++) {
while (!q1.empty()) {
int cur = q1.front();
q1.pop(), inqueue1[cur] = false;
for (auto& next : AdjList[cur]) {
if (distance[next.first] > distance[cur] + next.second) { // 可以進行relax
distance[next.first] = distance[cur] + next.second; // 最短路徑為
predecessor[next.first] = cur; // 父節點為cur
if (!inqueue2[next.first]) { // 放進q2，給下輪更新
q2.push(next.first);
inqueue2[next.first] = true;
}
}
}
} // while queue not empty
q1.swap(q2), inqueue1.swap(inqueue2);
} // at most v_num-1 edges
if (!q1.empty()) cout << "negative cycle exists";
printData(distance, "distance");
printData(predecessor, "predecessor");
/*
int End = v_num - 1;
for (int i = End; i != Start; i = predecessor[i]) {
cout << i << ' ';
} cout << Start << '\n';
*/
} // SSSP_BF
void SSSP_Dijkstra(int Start) {
color.resize(v_num, 0); // 走訪狀態
distance.resize(v_num, INT_MAX); // 與Start的距離
predecessor.resize(v_num, -1); // 父節點
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
if (color[Start] == 0) {
color[Start] = 1; // 走訪中
distance[Start] = 0; // 起始點距離為0
predecessor[Start] = -1; // 起始點沒有父節點
q.push(make_pair(Start, 0));
while (!q.empty()) {
pair<int, int> cur = q.top();
q.pop();
if (color[cur.first] != 2) {
for (auto& next : AdjList[cur.first]) {
if (distance[next.first] > distance[cur.first] + next.second) {
color[next.first] = 1; // 走訪中
distance[next.first] = distance[cur.first] + next.second; // 最短路徑為
predecessor[next.first] = cur.first; // 父節點為cur
q.push(make_pair(next.first, distance[next.first]));
}
}
color[cur.first] = 2; // 走訪完畢
} // not visited
} // while queue not empty
}
printData(color, "color");
printData(distance, "distance");
printData(predecessor, "predecessor");
/*
int End = v_num - 1;
for (int i = End; i != Start; i = predecessor[i]) {
cout << i << ' ';
} cout << Start << '\n';
*/
} // SSSP_BF
void FloydWarshall() {
vector<vector<int>> distance2D(v_num, vector<int>(v_num, INT_MAX));
vector<vector<int>> predecessor2D(v_num, vector<int>(v_num, -1));
for (int i = 0; i < v_num; i++) {
distance2D[i][i] = 0;
for (auto& next : AdjList[i]) {
distance2D[i][next.first] = next.second;
predecessor2D[i][next.first] = i;
}
}
for (int k = 0; k < v_num; k++) { // 增加 k-th 點
for (int i = 0; i < v_num; i++) { // 跑過所有 i to j
for (int j = 0; j < v_num; j++) {
if (distance2D[i][k] != INT_MAX && distance2D[k][j] != INT_MAX &&
distance2D[i][j] > distance2D[i][k] + distance2D[k][j]) {
distance2D[i][j] = distance2D[i][k] + distance2D[k][j];
predecessor2D[i][j] = predecessor2D[k][j];
}
}
}
}
printData2D(distance2D, "distance");
printData2D(predecessor2D, "predecessor");
/*
int Start = 0;
int End = v_num - 1;
while (predecessor2D[Start][End] != -1) {
cout << End << ' ';
End = predecessor2D[Start][End];
} cout << Start << '\n';
*/
} // FloydWarshall
// 限用在無向圖
void ConnectedTreeDFS(int cur, int& deep, vector<int>& ap, vector<pair<int, int>>& bridge) {
int child = 0;
low[cur] = dep[cur] = ++deep; // 紀錄當前深度
for (auto& next : AdjList[cur]) {
if (next.first == predecessor[cur]) continue; // 是父節點
if (dep[next.first] == 0) { // 還沒走過
child++;
predecessor[next.first] = cur; // 父節點為cur
ConnectedTreeDFS(next.first, deep, ap, bridge);
low[cur] = min(low[cur], low[next.first]); // 能到達的最小深度
if (low[next.first] >= dep[cur]) { // child能到達的最小深度 >= cur
if (predecessor[cur] != -1) ap.emplace_back(cur);
if (low[next.first] > dep[cur]) bridge.emplace_back(cur, next.first);
}
}
else low[cur] = min(low[cur], dep[next.first]); // 有一條back edge
}
if (predecessor[cur] == -1 && child > 1) ap.emplace_back(cur);
--deep; // 回到先前深度
} // DFSVisit
void DFS_tree(int Start) {
predecessor.resize(v_num, -1); // 父節點
dep.resize(v_num, 0); // dfs tree 深度
low.resize(v_num, INT_MAX); // 先往子孫走，再通過不超過一次的 back edge，
// 所能達到的節點的最小深度
vector<int> ap;
vector<pair<int, int>> bridge;
int deep = 0;
if (dep[Start] == 0)
ConnectedTreeDFS(Start, deep, ap, bridge);
// 避免不連通的清況
for (int i = 0; i < v_num; i++) {
if (dep[i] == 0)
ConnectedTreeDFS(i, deep, ap, bridge);
} // for all
printData(predecessor, "predecessor");
printData(dep, "dep");
printData(low, "low");
cout << "ap:\n";
for (auto& i : ap) cout << i << ' ';
cout << "\nbridge:\n";
for (auto& i : bridge) cout << i.first << ',' << i.second << '\n';
} // DFS_tree
// 限用在無向圖
int ConnectedHeavyDFS(int cur, int& deep, long long dis) {
dep[cur] = ++deep; // 紀錄當前深度
distance[cur] = dis;
int max = 0; // 此鏈最大長度
int total = 1; // 此點(包含)以下的總結點數
for (auto& next : AdjList[cur]) {
if (next.first == predecessor[cur]) continue; // 是父節點
if (dep[next.first] == 0) { // 還沒走過
predecessor[next.first] = cur; // 父節點為cur
int next_total = ConnectedHeavyDFS(next.first, deep, dis + next.second); // 取得子節點的總數
if (next_total > max) { // 選出最重的子點
max = next_total, heavy[cur] = next.first; // 紀錄最重的資訊
}
total += next_total;
}
}
deep--; // 回到先前深度
return total;
} // ConnectedHeavyDFS
void ConnectedHeadDFS(int cur, int head_index) {
head[cur] = head_index;
for (auto& next : AdjList[cur]) {
if (next.first == predecessor[cur]) continue; // 是父節點
if (next.first == heavy[cur])
ConnectedHeadDFS(next.first, head_index); // 走比較重的那側
else ConnectedHeadDFS(next.first, next.first); // 走比較輕的那側
}
} // ConnectedHeadDFS(decompose)
void HLD(int Start) { // Heavy-Light Decomposition
predecessor.resize(v_num, -1); // 父節點
dep.resize(v_num, 0); // dfs tree 深度
heavy.resize(v_num, -1); // 最重的子點代號
head.resize(v_num, -1); // 每條鍊的初始點
distance.resize(v_num, -1); // 距離
int deep = 0;
int dis = 0;
ConnectedHeavyDFS(Start, deep, dis);
ConnectedHeadDFS(Start, Start);
// printData(predecessor, "predecessor");
// printData(dep, "dep");
// printData(distance, "distance");
// printData(heavy, "heavy");
// printData(head, "head");
} // HLD
int LCA(int n1, int n2) {
while (head[n1] != head[n2]) { // 兩條鏈的起始點不同
// 找較深的鏈，到其上一條鏈
if (dep[head[n1]] > dep[head[n2]]) n1 = predecessor[head[n1]];
else n2 = predecessor[head[n2]];
if (n1 == -1 || n2 == -1) return -1; // 找不到
}
// n1 和 n2 在同一條鏈，選深度較淺的
if (dep[n1] < dep[n2]) return n1;
else return n2;
} // LCA
// 限用在無向圖
bool BFS_bi() {
color.resize(v_num, -1); // 塗色狀態
for (int Start = 0; Start < v_num; Start++) {
if (color[Start] == -1) {
queue<int> q;
int c = 0; // 色(0, 1)
color[Start] = c; // 上色
q.push(Start);
while (!q.empty()) {
int cur = q.front();
q.pop();
c = color[cur]; // 父點的色
for (auto& next : AdjList[cur]) {
if (color[next.first] == -1) { // 未塗色
color[next.first] = !c; // 上色
q.push(next.first);
}
else if (color[next.first] == c)
return false; // 與父點同色
}
} // while queue not empty
} // not visited
} // for all
return true;
} // ConnectedBFS_bi
tuple<int,int,vector<list<int>>> GetBIG() {
i2bi.resize(v_num);
bi2i.resize(2, vector<int>());
for (int i = 0; i < v_num; i++) {
i2bi[i].first = color[i];
i2bi[i].second = bi2i[color[i]].size();
bi2i[color[i]].push_back(i);
}
vector<list<int>> result;
result.resize(bi2i[0].size());
for (int cur = 0; cur < v_num; cur++) {
if (i2bi[cur].first) continue;
for (auto& next : AdjList[cur]) {
result[i2bi[cur].second].push_back(i2bi[next.first].second);
}
}
return make_tuple(bi2i[0].size(), bi2i[0].size(), result);
} // GetBIG
void GetMatch(vector<pair<int, int>> result) {
for (auto& i : result) {
cout << bi2i[0][i.first] << ' '
<< bi2i[1][i.second] << '\n';
}
} // GetMatch
};
class BipGraph {
int L_num, R_num;
vector< list<int> > AdjList;
vector<int> pairL2R;
vector<int> pairR2L;
vector<int> distance;
public:
BipGraph() :L_num(0), R_num(0) {};
BipGraph(int L, int R) :L_num(L), R_num(R) {
AdjList.resize(L);
};
BipGraph(tuple<int, int, vector<list<int>>>& g) {
L_num = get<0>(g);
R_num = get<1>(g);
AdjList = get<2>(g);
};
void AddEdgeList(int from, int to) {
AdjList[from].push_back(to);
} // AddEdgeList
// 限用在2分無向圖
bool HopcroftKarp_BFS() {
queue<int> q;
for (int i = 0; i < L_num; i++) {
// 如果未被配對到，可以做為起點
if (pairL2R[i] == L_num) {
distance[i] = 0; // 距離為0
q.push(i); // 放進Q準備BFS
}
// 已被配對過
else distance[i] = INT_MAX; // 距離為最大值
} // init BFS
// 建立一個虛擬的點，假裝已經被配對過
// pairR2L 未配對到，會指向這個點
// 當此值被修改時，表示找到第一個 aug path
// 因此也表示[目前最小 BFS 深度]，初值為最大值
distance[L_num] = INT_MAX;
while (!q.empty()) {
int cur = q.front();
q.pop();
// 比[目前最小 BFS 深度]來的小
if (distance[cur] < distance[L_num]) {
for (auto& next : AdjList[cur]) {
// 這個點已被配對過，且在此輪還沒有走訪過
if (distance[pairR2L[next]] == INT_MAX) {
distance[pairR2L[next]] = distance[cur] + 1; // 紀錄這個點的距離，給 DFS 走訪用
q.push(pairR2L[next]); // 可以繼續 BFS
}
}
}
} // while queue not empty
// 如果[目前最小 BFS 深度]不是INT_MAX，表示有 aug path
if (distance[L_num] != INT_MAX) return true;
else return false;
} // HopcroftKarp_BFS
bool HopcroftKarp_DFS(int cur) {
if (cur == L_num) return true; // 找到一個未配對的點，存在aug path
else {
for (auto& next : AdjList[cur]) {
if (distance[pairR2L[next]] == distance[cur] + 1 && // 找到 BFS 留下的記號
HopcroftKarp_DFS(pairR2L[next])) { // aug path 還存在
pairL2R[cur] = next; // 紀錄 L2R
pairR2L[next] = cur; // 紀錄 R2L
return true; // 存在aug path
}
}
// 找不到一個未配對的點 (原本存在，被用掉了)
distance[cur] = INT_MAX; // 覆蓋掉 BFS 的資訊
return false; // 不存在aug path
}
} // HopcroftKarp_DFS
vector<pair<int, int>> HopcroftKarp() {
// 初值為 L_num 表示沒有配對對象
pairL2R.resize(L_num, L_num);
pairR2L.resize(R_num, L_num);
// 紀錄 left 點 BFS 的距離，初值為 0 (right 不算)
// L_num+1 因為有包含一個虛擬的點(index = L_num)，未配對前都指向他
distance.resize(L_num + 1, 0);
// 由 BFS 紀錄 distance，DFS 根據 distance 找到配對點
// 若 BFS() = true，表示有 aug path
while (HopcroftKarp_BFS()) {
for (int i = 0; i < L_num; i++) {
if (pairL2R[i] == L_num) // 沒有配對過
HopcroftKarp_DFS(i); // 且有 aug path 存在 (有可能被其他用掉)
}
}
// make pair
vector<pair<int, int>> result;
result.reserve(min(L_num, R_num));
for (int i = 0; i < L_num; i++) {
if (pairL2R[i] != L_num)
result.push_back(make_pair(i, pairL2R[i]));
}
return result;
} // HopcroftKarp
};
class Address {
public:
int x;
int y;
Address() :x(-1), y(-1) {}
Address(int a, int b) :x(a), y(b) {}
Address operator + (const Address& op2) const {
Address res;
res.x = x + op2.x;
res.y = y + op2.y;
return res;
}
Address operator - (const Address& op2) const {
Address res;
res.x = x - op2.x;
res.y = y - op2.y;
return res;
}
bool operator == (const Address& op2) const {
return (x == op2.x && y == op2.y);
}
friend ostream& operator << (ostream& out, const Address& op) {
out << '(' << setw(2) << op.x << ',' << setw(2) << op.y << ')';
return out;
}
};
class Node {
public:
int color; // 0:未走訪, 1:走訪中, 2:走訪完畢
int state; // -1:不能走, 0:可以走
int distance;
int discover;
int finish;
Address predecessor;
int size;
Node() {
color = false;
state = -1;
distance = INT_MAX;
discover = 0;
finish = 0;
predecessor = Address();
};
};
class Graph_map {
private:
int x, y; // will add border (+2)
Node** mapp;
Address around_4[4] =
{ Address(-1,0), Address(0,1), Address(1,0), Address(0,-1) }; // 順時針
Address around_8[8] =
{ Address(-1,0), Address(-1,1), Address(0,1), Address(1,1),
Address(1,0), Address(1,-1), Address(0,-1), Address(-1,-1) }; // 順時針
public:
Graph_map(int row, int column) :x(row + 2), y(column + 2) {
mapp = new Node * [x];
for (int i = 0; i < x; i++)
mapp[i] = new Node[y];
};
void readMap(bool include_broder) {
char input;
int state;
if (include_broder) {
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
cin >> input;
if (input == '#') mapp[i][j].state = -1;
else mapp[i][j].state = 0;
}
}
} // include_broder
else { // uninclude_broder
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
cin >> input;
if (input == '#') mapp[i][j].state = -1;
else mapp[i][j].state = 0;
}
}
} // uninclude_broder
} // readMap
void printMap(bool predecessor = false, bool distance = false, bool discover_finish = false) {
int n = 0;
if (distance) n += 2;
if (predecessor) n += 2;
if (discover_finish) n += 7;
cout << setw(2) << ' ';
for (int j = 0; j < y; j++)
cout << setw(n) << j << ' ';
cout << '\n';
for (int i = 0; i < x; i++) {
cout << setw(2) << i;
for (int j = 0; j < y; j++) {
if (mapp[i][j].state == 0) {
if (predecessor) {
Address cur(i, j);
cur = mapp[i][j].predecessor - cur;
if (cur == Address(-1, 0)) cout << "↑";
else if (cur == Address(0, 1)) cout << "→";
else if (cur == Address(1, 0)) cout << "↓";
else if (cur == Address(0, -1)) cout << "←";
else cout << " ";
} // predecessor
if (distance) {
cout << setw(2) << mapp[i][j].distance;
} // distance
if (discover_finish) {
cout << '(' << setw(2) << mapp[i][j].discover
<< ',' << setw(2) << mapp[i][j].finish << ')';
} // discover_finish
if (!(predecessor | distance | discover_finish)) cout << ' ';
cout << ' ';
}
else {
cout << setw(n) << '#' << ' ';
}
}
cout << '\n';
}
} // printMap
void ConnectedBFS(Address Start) {
queue<Address> q;
if (mapp[Start.x][Start.y].state == 0 &&
mapp[Start.x][Start.y].color == 0) {
mapp[Start.x][Start.y].color = 1; // 走訪中
mapp[Start.x][Start.y].distance = 0; // 起始點距離為0
mapp[Start.x][Start.y].predecessor = Address(-1, -1); // 起始點沒有父節點
q.push(Address(Start.x, Start.y));
while (!q.empty()) {
Address cur = q.front();
for (auto next : around_4) {
next = cur + next;
if (mapp[next.x][next.y].state == 0 &&
mapp[next.x][next.y].color == 0) {
mapp[next.x][next.y].color = 1; // 走訪中
mapp[next.x][next.y].distance =
mapp[cur.x][cur.y].distance + 1; // 距離為cur+1
mapp[next.x][next.y].predecessor = cur; // 父節點為cur
q.push(next);
}
}
mapp[cur.x][cur.y].color = 2; // 走訪完畢
q.pop();
} // while queue not empty
} // connected BFS end
} // ConnectedBFS
void BFS(Address Start) {
ConnectedBFS(Start);
// 避免不連通的清況
for (int i = 1; i < x - 1; i++) {
for (int j = 1; j < y - 1; j++) {
ConnectedBFS(Address(i, j));
} // for all
} // for all
// printMap();
} // BFS
void DFS_recursion(Address cur, int& time) {
mapp[cur.x][cur.y].color = 1; // 走訪中
mapp[cur.x][cur.y].discover = ++time; // 紀錄發現時間
for (auto next : around_4) {
next = cur + next;
if (mapp[next.x][next.y].state == 0 &&
mapp[next.x][next.y].color == 0) {
mapp[next.x][next.y].color = 1; // 走訪中
mapp[next.x][next.y].predecessor = cur; // 父節點為cur
DFS_recursion(next, time);
}
}
mapp[cur.x][cur.y].finish = ++time; // 紀錄完成時間
mapp[cur.x][cur.y].color = 2; // 走訪完畢
} // DFSVisit
void DFS(Address Start) {
int time = 0;
if (mapp[Start.x][Start.y].state == 0 &&
mapp[Start.x][Start.y].color == 0)
DFS_recursion(Start, time);
// 避免不連通的清況
for (int i = 1; i < x - 1; i++) {
for (int j = 1; j < y - 1; j++) {
if (mapp[i][j].state == 0 &&
mapp[i][j].color == 0)
DFS_recursion(Address(i, j), time);
} // for all
} // for all
// printMap();
} // DFS
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// http://alrightchiu.github.io/SecondRound/mu-lu-yan-suan-fa-yu-zi-liao-jie-gou.html
// https://hackmd.io/@nckuacm/NCKU-AdvCP-2021-Materials/https%3A%2F%2Fhackmd.io%2F%40XDEv11%2FNCKU-AdvCP-2021-Graph3#2021-Week12---Graph-BCC-SCC-LCA
// BFS
Graph_adj g1(9);
g1.AddEdgeList(0, 1); g1.AddEdgeList(0, 2); g1.AddEdgeList(0, 3);
g1.AddEdgeList(1, 0); g1.AddEdgeList(1, 4);
g1.AddEdgeList(2, 0); g1.AddEdgeList(2, 4); g1.AddEdgeList(2, 5); g1.AddEdgeList(2, 6); g1.AddEdgeList(2, 7);
g1.AddEdgeList(3, 0); g1.AddEdgeList(3, 7);
g1.AddEdgeList(4, 1); g1.AddEdgeList(4, 2); g1.AddEdgeList(4, 5);
g1.AddEdgeList(5, 2); g1.AddEdgeList(5, 4);
g1.AddEdgeList(6, 2); g1.AddEdgeList(6, 7);
g1.AddEdgeList(7, 2); g1.AddEdgeList(7, 3); g1.AddEdgeList(7, 6);
g1.AddEdgeList(8, 5); g1.AddEdgeList(8, 6);
g1.BFS(0);
// DFS
Graph_adj g2(8);
g2.AddEdgeList(0, 1); g2.AddEdgeList(0, 2);
g2.AddEdgeList(1, 3);
g2.AddEdgeList(2, 1); g2.AddEdgeList(2, 5);
g2.AddEdgeList(3, 4); g2.AddEdgeList(3, 5);
g2.AddEdgeList(5, 1);
g2.AddEdgeList(6, 4); g2.AddEdgeList(6, 7);
g2.AddEdgeList(7, 6);
g2.DFS(0);
// TopologicalSort
g2.getDecreaseFinish();
// SCC
Graph_adj g3(9);
g3.AddEdgeList(0, 1);
g3.AddEdgeList(1, 2); g3.AddEdgeList(1, 4);
g3.AddEdgeList(2, 0); g3.AddEdgeList(2, 3); g3.AddEdgeList(2, 5);
g3.AddEdgeList(3, 2);
g3.AddEdgeList(4, 5); g3.AddEdgeList(4, 6);
g3.AddEdgeList(5, 4); g3.AddEdgeList(5, 6); g3.AddEdgeList(5, 7);
g3.AddEdgeList(6, 7);
g3.AddEdgeList(7, 8);
g3.AddEdgeList(8, 6);
g3.DFS(0);
Graph_adj g4 = g3.GraphTranspose();
vector<int> finish = g3.getDecreaseFinish();
g4.DFS_order(finish);
g4.SetCollapsing();
// Graph_map BFS
/* n = 9
#########
#.......#
#.#####.#
#.......#
##.#.####
#..#.#..#
#.##.##.#
#.......#
#########
*/
Graph_map g5(7, 7);
g5.readMap(true);
g5.BFS(Address(1, 1));
g5.printMap(true, true, false);
// Graph_map DFS
/* n = 9
#########
#.......#
#.#####.#
#.......#
##.#.####
#..#.#..#
#.##.##.#
#.......#
#########
*/
Graph_map g6(7, 7);
g6.readMap(true);
g6.DFS(Address(1, 1));
g6.printMap(true, false, true);
// MST
Graph_adj g7(7);
g7.AddEdgeList(0, 1, 5); g7.AddEdgeList(0, 5, 3);
g7.AddEdgeList(1, 0, 5); g7.AddEdgeList(1, 2, 10); g7.AddEdgeList(1, 4, 1); g7.AddEdgeList(1, 6, 4);
g7.AddEdgeList(2, 1, 10); g7.AddEdgeList(2, 3, 5); g7.AddEdgeList(2, 6, 8);
g7.AddEdgeList(3, 2, 5); g7.AddEdgeList(3, 4, 7); g7.AddEdgeList(3, 6, 9);
g7.AddEdgeList(4, 1, 1); g7.AddEdgeList(4, 3, 7); g7.AddEdgeList(4, 5, 6); g7.AddEdgeList(4, 6, 2);
g7.AddEdgeList(5, 0, 3); g7.AddEdgeList(5, 4, 6);
g7.AddEdgeList(6, 1, 4); g7.AddEdgeList(6, 2, 8); g7.AddEdgeList(6, 3, 9); g7.AddEdgeList(6, 4, 2);
g7.MST_Prims(2);
// SSSP Bellman-Ford 可負weigh, 可負weight cycle
Graph_adj g8(6);
g8.AddEdgeList(0, 1, 5);
g8.AddEdgeList(1, 4, -4); g8.AddEdgeList(1, 2, 6);
g8.AddEdgeList(2, 4, -3); g8.AddEdgeList(2, 5, -2);
g8.AddEdgeList(3, 2, 4);
g8.AddEdgeList(4, 3, 1); g8.AddEdgeList(4, 5, 6);
g8.AddEdgeList(5, 0, 3); g8.AddEdgeList(5, 1, 7);
g8.SSSP_BF(0);
// SSSP Dijkstra 不可負weigh, 不可負weight cycle
Graph_adj g9(6);
g9.AddEdgeList(0, 1, 8); g9.AddEdgeList(0, 5, 1);
g9.AddEdgeList(1, 0, 3); g9.AddEdgeList(1, 2, 1);
g9.AddEdgeList(2, 0, 5); g9.AddEdgeList(2, 3, 2); g9.AddEdgeList(2, 4, 2);
g9.AddEdgeList(3, 1, 4); g9.AddEdgeList(3, 2, 6); g9.AddEdgeList(3, 4, 7); g9.AddEdgeList(3, 5, 3);
g9.AddEdgeList(5, 3, 2); g9.AddEdgeList(5, 4, 8);
g9.SSSP_Dijkstra(0);
// ALL SSSP FloydWarshall 可負weigh, 不可負weight cycle
Graph_adj g10(4);
g10.AddEdgeList(0, 1, 2); g10.AddEdgeList(0, 2, 6); g10.AddEdgeList(0, 3, 8);
g10.AddEdgeList(1, 2, -2); g10.AddEdgeList(1, 3, 3);
g10.AddEdgeList(2, 0, 4); g10.AddEdgeList(2, 3, 1);
g10.FloydWarshall();
// DFS_tree
Graph_adj g11(6);
g11.AddEdgeList(0, 1, 1, true);
g11.AddEdgeList(1, 2, 1, true); g11.AddEdgeList(1, 3, 1, true);
g11.AddEdgeList(2, 3, 1, true);
g11.AddEdgeList(3, 4, 1, true); g11.AddEdgeList(3, 5, 1, true);
g11.AddEdgeList(4, 5, 1, true);
g11.DFS_tree(0);
// DFS_heavy_light
Graph_adj g12(14);
g12.AddEdgeList(0, 1, 1, true); g12.AddEdgeList(1, 2, 1, true); g12.AddEdgeList(2, 4, 1, true); g12.AddEdgeList(4, 5, 1, true);
g12.AddEdgeList(2, 3, 1, true);
g12.AddEdgeList(1, 6, 1, true);
g12.AddEdgeList(0, 7, 1, true); g12.AddEdgeList(7, 8, 1, true); g12.AddEdgeList(8, 9, 1, true);
g12.AddEdgeList(0, 10, 1, true); g12.AddEdgeList(10, 11, 1, true);
g12.AddEdgeList(10, 12, 1, true);
g12.AddEdgeList(10, 13, 1, true);
g12.HLD(0);
cout << g12.LCA(3, 6) << '\n';
cout << g12.LCA(9, 13) << '\n';
// bi graph match
Graph_adj g13(8);
g13.AddEdgeList(0, 3, 1, true);
g13.AddEdgeList(0, 5, 1, true);
g13.AddEdgeList(2, 1, 1, true);
g13.AddEdgeList(4, 3, 1, true);
g13.AddEdgeList(6, 3, 1, true);
g13.AddEdgeList(6, 7, 1, true);
if (g13.BFS_bi()) {
tuple<int, int, vector<list<int>>> bi_adj = g13.GetBIG();
BipGraph g14(bi_adj);
vector<pair<int, int>> match = g14.HopcroftKarp();
g13.GetMatch(match);
}
else cout << "not bi graph\n";
return 0;
}
```
### merge sort
```c++=1
#include <iostream>
using namespace std;
void merge(int arr[], int l, int r, int m) {
int lenA = m - l + 1;
int lenB = r - m;
int a[lenA] = {0};
int b[lenB] = {0};
for (int i = 0; i < lenA; i++)
a[i] = arr[l+i];
for (int i = 0; i < lenB; i++)
b[i] = arr[m+1+i];
int i = 0, j = 0, k = l;
while (i < lenA && j < lenB) {
if (a[i] < b[j]) {
arr[k] = a[i];
i++;
} else {
arr[k] = b[j];
j++;
}
k++;
}
while (i < lenA) {
arr[k] = a[i];
i++;
k++;
}
while (j < lenB) {
arr[k] = b[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, r, m);
}
}
int main() {
int N;
cin >> N;
int a[N] = {0};
for (int i = 0; i < N; i++)
cin >> a[i];
mergeSort(a, 0, N-1);
for (int i = 0; i < N; i++)
cout << a[i] << " ";
cout << '\n';
return 0;
}
```
### heap sort
```C++=1
#include <iostream>
using namespace std;
//i = 0...N
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i+1;
int r = 2*i+2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
swap(arr[largest], arr[i]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n/2-1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n-1; i >= 1; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
heapSort(a, n);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
```
### radix sort
```c++=1
// implementation of radix sort using bin/bucket sort
#include <bits/stdc++.h>
using namespace std;
// structure for a single linked list to help further in the
// sorting
struct node {
int data;
node* next;
};
// function for creating a new node in the linked list
struct node* create(int x)
{
node* temp = new node();
temp->data = x;
temp->next = NULL;
return temp;
}
// utility function to append node in the linked list
// here head is passed by reference, to know more about this
// search pass by reference
void insert(node*& head, int n)
{
if (head == NULL) {
head = create(n);
return;
}
node* t = head;
while (t->next != NULL)
t = t->next;
t->next = create(n);
}
// utility function to pop an element from front in the list
// for the sake of stability in sorting
int del(node*& head)
{
if (head == NULL)
return 0;
node* temp = head;
// storing the value of head before updating
int val = head->data;
// updation of head to next node
head = head->next;
delete temp;
return val;
}
// utility function to get the number of digits in the
// max_element
int digits(int n)
{
int i = 1;
if (n < 10)
return 1;
while (n > (int)pow(10, i))
i++;
return i;
}
void radix_sort(vector<int>& arr)
{
// size of the array to be sorted
int sz = arr.size();
// getting the maximum element in the array
int max_val = *max_element(arr.begin(), arr.end());
// getting digits in the maximum element
int d = digits(max_val);
// creating buckets to store the pointers
node** bins;
// array of pointers to linked list of size 10 as
// integers are decimal numbers so they can hold numbers
// from 0-9 only, that's why size of 10
bins = new node*[10];
// initializing the hash array with null to all
for (int i = 0; i < 10; i++)
bins[i] = NULL;
// first loop working for a constant time only and inner
// loop is iterating through the array to store elements
// of array in the linked list by their digits value
for (int i = 0; i < d; i++) {
for (int j = 0; j < sz; j++) // bins updation
insert(bins[(arr[j] / (int)pow(10, i)) % 10],
arr[j]);
int x = 0, y = 0;
// write back to the array after each pass
while (x < 10) {
while (bins[x] != NULL)
arr[y++] = del(bins[x]);
x++;
}
}
}
// a utility function to print the sorted array
void print(vector<int> arr)
{
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
vector<int> arr = { 573, 25, 415, 12, 161, 6 };
// function call
radix_sort(arr);
print(arr);
return 0;
}
```
### shell sort
```c++=1
void swap(int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b= temp;
};
int shell_sort(int A[], int n){
int span, i;
span = n/2;
while(span>=1){
for(i = 0; i<(n-span); i++){
if(A[i]>A[i+span]){
swap(&A[i], &A[i+span]);
}
}
span = span/2;
}
};
int main(){
int count, i;
scanf("%d", &count);
int list[count];
printf("Numbers to be sorted: ");
for(i = 0; i<count; i++){
scanf("%d", &list[i]);
printf("%d ", list[i]);
}
printf("\n");
shell_sort(list, count);
printf("Numbers Sorted: ");
for(i = 0; i<count; i++){
printf("%d ", list[i]);
}
return 0;
}
```
### GCD
```c++=1
int gcd(int a, int b) {
while (b) {
int r = a % b;
a = b;
b = r;
}
return a;
}
```
### 終極密碼 (猜能成功的最小答案)
```c++=1
bool simulate(const int& a, const int& t) {
// success -> true
// fail -> false
return a > t;
}
int guess(vector<int> &data, int target) {
auto begin = data.begin();
auto end = data.end();
sort(data.begin(), data.end()); // increase (default)
// data.begin()+1 ~ data.end() may be ans, no data.begin()
while (end - begin > 1) {
auto mid = begin + (end - begin)/2;
// success
if (simulate(*mid, target)) end = mid;
// fail
else begin = mid;
}
if (end == data.end()) return -1;
else return *end; // min success
}
```
### 大數運算
``` C++=1
//#include<cstring>
//讀取大數
void scan(char s[100], int a[100])
{
int i = 100 - 1;
int j = 0, n = strlen(s);
while (i >= n) a[i--] = 0;
while (i >= 0) a[i--] = s[j++] - '0';
}
//印出大數
void print(int a[100])
{
int i = 100 - 1;
while (i >= 0 && a[i] == 0) i--;
if (i < 0)
cout << '0';
else
while (i >= 0) cout << a[i--];
}
//比較大小
bool largerthan(int a[100], int b[100])
{
for (int i=100-1; i>=0; i--)
if (a[i] != b[i]) 。
return a[i] > b[i];
return false;
}
//大數加法
void add(int a[100], int b[100], int c[100])
{
for (int i=0; i<100; i++)
c[i] = a[i] + b[i];
for (int i=0; i<100-1; i++)
{
c[i+1] += c[i] / 10;
c[i] %= 10;
}
}
//大數減法
void sub(int a[100], int b[100], int c[100])
{
for (int i=0; i<100; i++)
c[i] = a[i] - b[i];
for (int i=0; i<100-1; i++)
if (c[i] < 0)
{
c[i+1]--;
c[i] += 10;
}
}
//大數乘法
void mul(int a[100], int b[100], int c[100])
{
for (int i=0; i<100; i++)
c[i] = 0;
for (int i=0; i<100; i++)
for (int j=0; j<100; j++)
if (i+j < 100)
c[i+j] += a[i] * b[j];
for (int i=0; i<100-1; i++)
{
c[i+1] += c[i] / 10;
c[i] %= 10;
}
}
void mul(int a[100], int b, int c[100])
{
for (int i=0; i<100; i++)
c[i] = a[i] * b;
for (int i=0; i<100-1; i++)
{
c[i+1] += c[i] / 10;
c[i] %= 10;
}
}
//大數除法
void div(int a[100], int b[100], int c[100])
{
int t[100];
for (int i=100-1; i>=0; i--)
for (int k=9; k>0; k--)
{
mul(b+i, k, t);
if (largerthan(a+i, t))
{
sub(a+i, t, c+i);
break;
}
}
}
void div(int a[100], int b, int c[100])
{
int r = 0;
for (int i=100-1; i>=0; i--)
{
r = r * 10 + a[i];
c[i] = r / b;
r %= b;
}
}
```
### Single Source Shortest Path
#### Bellmon Ford
``` C++
// A C++ program for Bellman-Ford's single source
// shortest path algorithm.
#include <bits/stdc++.h>
// a structure to represent a weighted edge in graph
struct Edge {
int src, dest, weight;
};
// a structure to represent a connected, directed and
// weighted graph
struct Graph {
// V-> Number of vertices, E-> Number of edges
int V, E;
// graph is represented as an array of edges.
struct Edge* edge;
};
// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
// A utility function used to print the solution
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
// The main function that finds shortest distances from src to
// all other vertices using Bellman-Ford algorithm. The function
// also detects negative weight cycle
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
// Step 1: Initialize distances from src to all other vertices
// as INFINITE
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
// Step 2: Relax all edges |V| - 1 times. A simple shortest
// path from src to any other vertex can have at-most |V| - 1
// edges
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
// Step 3: check for negative-weight cycles. The above step
// guarantees shortest distances if graph doesn't contain
// negative weight cycle. If we get a shorter path, then there
// is a cycle.
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return; // If negative cycle is detected, simply return
}
}
printArr(dist, V);
return;
}
// Driver program to test above functions
int main()
{
/* Let us create the graph given in above example */
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
// add edge 0-1 (or A-B in above figure)
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
// add edge 1-4 (or A-E in above figure)
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
}
```
#### Dijskstra's
```C++
// A C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph
#include <limits.h>
#include <stdio.h>
// Number of vertices in the graph
#define V 9
// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// A utility function to print the constructed distance array
int printSolution(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
// Function that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i
bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in the first iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
printSolution(dist, V);
}
// driver program to test above function
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
dijkstra(graph, 0);
return 0;
}
```
### All Path Shortest Path
#### Floyd-Washall
``` C++
// C++ Program for Floyd Warshall Algorithm
#include <bits/stdc++.h>
using namespace std;
// Number of vertices in the graph
#define V 4
/* Define Infinite as a large enough
value.This value will be used for
vertices not connected to each other */
#define INF 99999
// A function to print the solution matrix
void printSolution(int dist[][V]);
// Solves the all-pairs shortest path
// problem using Floyd Warshall algorithm
void floydWarshall(int graph[][V])
{
/* dist[][] will be the output matrix
that will finally have the shortest
distances between every pair of vertices */
int dist[V][V], i, j, k;
/* Initialize the solution matrix same
as input graph matrix. Or we can say
the initial values of shortest distances
are based on shortest paths considering
no intermediate vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
/* Add all vertices one by one to
the set of intermediate vertices.
---> Before start of an iteration,
we have shortest distances between all
pairs of vertices such that the
shortest distances consider only the
vertices in set {0, 1, 2, .. k-1} as
intermediate vertices.
----> After the end of an iteration,
vertex no. k is added to the set of
intermediate vertices and the set becomes {0, 1, 2, ..
k} */
for (k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (i = 0; i < V; i++) {
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++) {
// If vertex k is on the shortest path from
// i to j, then update the value of
// dist[i][j]
if (dist[i][j] > (dist[i][k] + dist[k][j])
&& (dist[k][j] != INF
&& dist[i][k] != INF))
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
printSolution(dist);
}
/* A utility function to print solution */
void printSolution(int dist[][V])
{
cout << "The following matrix shows the shortest "
"distances"
" between every pair of vertices \n";
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
cout << "INF"
<< " ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
}
// Driver code
int main()
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
int graph[V][V] = { { 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 } };
// Print the solution
floydWarshall(graph);
return 0;
}
// This code is contributed by Mythri J L
```
### hungarian algorithm
``` C++
#include<vector>
#include<queue>
#include<limits>
#include<iostream>
using namespace std;
// Hungarian Algorithm - O(V^3)
class WeightedBipartiteMatching {
int n;
vector<long long> lx{}, ly{};
vector<bool> vx{}, vy{};
queue<int> qu{}; // only X's vertices
vector<int> py{};
vector<long long> dy{}; // smallest (lx[x] + ly[y] - w[x][y])
vector<int> pdy{}; // & which x
vector<int> mx{}, my{};
void relax(const vector<vector<long long>>& w, int x) {
for (int y{0}; y < n; ++y)
if (lx[x] + ly[y] - w[x][y] < dy[y])
dy[y] = lx[x] + ly[y] - w[x][y], pdy[y] = x;
}
void augment(int y) {
while (y != -1) {
int x{py[y]}, yy{mx[x]};
mx[x] = y, my[y] = x;
y = yy;
}
}
bool bfs(const vector<vector<long long>>& w) {
while (!qu.empty()) {
int x{qu.front()}; qu.pop();
for (int y{0}; y < n; ++y) {
if (!vy[y] && lx[x] + ly[y] == w[x][y]) {
vy[y] = true, py[y] = x;
if (my[y] == -1) return augment(y), true;
int xx{my[y]};
qu.push(x), vx[xx] = true, relax(w, xx);
}
}
}
return false;
}
void relabel() {
long long d{numeric_limits<long long>::max()};
for (int y{0}; y < n; ++y) if (!vy[y]) d = min(d, dy[y]);
for (int x{0}; x < n; ++x) if (vx[x]) lx[x] -= d;
for (int y{0}; y < n; ++y) if (vy[y]) ly[y] += d;
for (int y{0}; y < n; ++y) if (!vy[y]) dy[y] -= d;
}
bool expand(const vector<vector<long long>>& w) { // expand one layer with new equality edges
for (int y{0}; y < n; ++y) {
if (!vy[y] && dy[y] == 0) {
vy[y] = true, py[y] = pdy[y];
if (my[y] == -1) return augment(y), true;
int xx{my[y]};
qu.push(xx), vx[xx] = true, relax(w, xx);
}
}
return false;
}
public:
pair<vector<int>, vector<int>> operator()(const vector<vector<long long>>& w) {
n = w.size(), lx.assign(n, 0), ly.assign(n, 0), vx.resize(n), vy.resize(n), py.resize(n), dy.resize(n), pdy.resize(n), mx.assign(n, -1), my.assign(n, -1);
for (int i{0}; i < n; ++i)
for (int j{0}; j < n; ++j)
lx[i] = max(lx[i], w[i][j]);
for (int x{0}; x < n; ++x) {
fill(vx.begin(), vx.end(), false);
fill(vy.begin(), vy.end(), false);
fill(dy.begin(), dy.end(), numeric_limits<long long>::max());
qu = {}, qu.push(x), vx[x] = true, relax(w, x);
while (!bfs(w)) {
relabel();
if (expand(w)) break;
}
}
return {move(mx), move(my)}; // mx 矩陣由上往下看選到的index my 矩陣由左往右看選到的index
}
};
int main(){
vector<vector<long long>> MM{{-2500,-4000,-3500}, {-4000,-6000,-3500}, {-2000,-4000,-2500}}; // 正數 -> 選最大匹配 ， 變負數 ->改成選最小匹配
pair<vector<int>,vector<int>> result;
class WeightedBipartiteMatching A;
int i,j;
for(i=0;i<3;i++){
for(j=0;j<3;j++){
cout << MM[i][j] <<' ';
}
cout << '\n';
}
result=A(MM);
for(i=0;i<3;i++){
cout << (result.first)[i]<<' ';
}
cout << '\n';
for(i=0;i<3;i++){
cout << (result.second)[i]<<' ';
}
return 0;
}
```
### 最大流量/最小切割
```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 << fordFulkerson(graph, 0, 5);
return 0;
}
```
### 🌸
``` C++
/*
GETS:
V->number of vertices
E->number of edges
pair of vertices as edges (vertices are 1..V)
GIVES:
output of edmonds() is the maximum matching
match[i] is matched pair of i (-1 if there isn't a matched pair)
*/
#include <bits/stdc++.h>
using namespace std;
const int M=500;
struct struct_edge{int v;struct_edge* n;};
typedef struct_edge* edge;
struct_edge pool[M*M*2];
edge top=pool,adj[M];
int V,E,match[M],qh,qt,q[M],father[M],base[M];
bool inq[M],inb[M],ed[M][M];
void add_edge(int u,int v)
{
top->v=v,top->n=adj[u],adj[u]=top++;
top->v=u,top->n=adj[v],adj[v]=top++;
}
int LCA(int root,int u,int v)
{
static bool inp[M];
memset(inp,0,sizeof(inp));
while(1)
{
inp[u=base[u]]=true;
if (u==root) break;
u=father[match[u]];
}
while(1)
{
if (inp[v=base[v]]) return v;
else v=father[match[v]];
}
}
void mark_blossom(int lca,int u)
{
while (base[u]!=lca)
{
int v=match[u];
inb[base[u]]=inb[base[v]]=true;
u=father[v];
if (base[u]!=lca) father[u]=v;
}
}
void blossom_contraction(int s,int u,int v)
{
int lca=LCA(s,u,v);
memset(inb,0,sizeof(inb));
mark_blossom(lca,u);
mark_blossom(lca,v);
if (base[u]!=lca)
father[u]=v;
if (base[v]!=lca)
father[v]=u;
for (int u=0;u<V;u++)
if (inb[base[u]])
{
base[u]=lca;
if (!inq[u])
inq[q[++qt]=u]=true;
}
}
int find_augmenting_path(int s)
{
memset(inq,0,sizeof(inq));
memset(father,-1,sizeof(father));
for (int i=0;i<V;i++) base[i]=i;
inq[q[qh=qt=0]=s]=true;
while (qh<=qt)
{
int u=q[qh++];
for (edge e=adj[u];e;e=e->n)
{
int v=e->v;
if (base[u]!=base[v]&&match[u]!=v)
if ((v==s)||(match[v]!=-1 && father[match[v]]!=-1))
blossom_contraction(s,u,v);
else if (father[v]==-1)
{
father[v]=u;
if (match[v]==-1)
return v;
else if (!inq[match[v]])
inq[q[++qt]=match[v]]=true;
}
}
}
return -1;
}
int augment_path(int s,int t)
{
int u=t,v,w;
while (u!=-1)
{
v=father[u];
w=match[v];
match[v]=u;
match[u]=v;
u=w;
}
return t!=-1;
}
int edmonds()
{
int matchc=0;
memset(match,-1,sizeof(match));
for (int u=0;u<V;u++)
if (match[u]==-1)
matchc+=augment_path(u,find_augmenting_path(u));
return matchc;
}
int main()
{
int u, v;
cin >> V >> E;
while(E--)
{
cin >> u >> v;
if (!ed[u-1][v-1])
{
add_edge(u-1,v-1);
ed[u-1][v-1] = ed[v-1][u-1] = true;
}
}
cout << edmonds() << endl;
for (int i = 0; i < V; i++)
if (i < match[i])
cout << i+1 << " " << match[i]+1 << endl;
}
```
🚰
``` C++
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
#define MAXN 100
#define INF 2147483647
#define ull unsigned long long
using namespace std;
struct MaxFlow{
struct edge{
int to, cap, flow;
ull 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));
while(df = dfs(s, INF)){
flow += df;
}
}
return flow;
}
void addedge(int st, int ed, int cap){
v[st].push_back(edge{ed, cap, 0, v[ed].size()});
v[ed].push_back(edge{st, 0, 0, v[st].size() - 1});
}
};
int main() {
MaxFlow maxflow;
maxflow.addedge(0, 1, 3);
maxflow.addedge(0, 2, 1);
maxflow.addedge(1, 2, 2);
maxflow.addedge(1, 3, 2);
maxflow.addedge(2, 3, 2);
cout << maxflow.maxflow(0, 3) << endl;
cout << "------" << endl;
MaxFlow maxflow2;
int n, e;
cin >> n >> e;
int s, t;
cin >> s >> t;
int u, v, cap;
for (int i = 0; i < e; i++) {
cin >> u >> v >> cap;
maxflow2.addedge(u, v, cap);
}
cout << maxflow2.maxflow(s, t) << endl;
}
```
Sign in with Wallet
Connect another wallet