代码模板集合

IO

用 fread 加速输入

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
namespace IN {
#define MAX_INPUT 100000
char buf[MAX_INPUT], *fs, *ft;
#define scanchar() (fs == ft ? (ft = (fs = buf) + fread(buf, 1, MAX_INPUT, stdin), fs == ft ? 0 : *fs++) : *fs++)
inline int read() {
int x = 0, y = 1;
char ch = scanchar();
while (!isdigit(ch)) {
if (ch == '-') y = -1;
ch = scanchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = scanchar();
}
return x * y;
}
#undef MAX_INPUT
#undef scanchar
}

用 putchar 加速输出

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
namespace OUT {
inline void put(int x) {
if (x == 0) {
putchar('0'); putchar('\n');
return;
}
if (x < 0) {
x = -x;
putchar('-');
}
char buf[11];
int top = 0;
while (x) {
buf[++top] = x % 10 + '0';
x /= 10;
}
while (top) putchar(buf[top--]);
putchar('\n');
}
}

用 sgetn 加速输入

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using std::cin;
namespace IN {
#define MAX_INPUT 100000
char buf[MAX_INPUT], *fs, *ft;
#define cinchar() (fs == ft ? (ft = (fs = buf) + fb -> sgetn(buf, MAX_INPUT), fs == ft ? 0 : *fs++) : *fs++)
inline int read() {
streambuf *fb(cin.rdbuf());
int x = 0, y = 1;
char ch = cinchar();
while (!isdigit(ch)) {
if (ch == '-') y = -1;
ch = cinchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = cinchar();
}
return x * y;
}
#undef MAX_INPUT
#undef cinchar
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}

用 sputc 加速输出

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using std::cout;
namespace OUT {
inline void put(int x) {
streambuf *fb(cout.rdbuf());
if (x == 0) {
fb -> sputc('0'); fb -> sputc('\n');
return;
}
if (x < 0) {
x = -x;
fb -> sputc('-');
}
char buf[11];
int top = 0;
while (x) {
buf[++top] = x % 10 + '0';
x /= 10;
}
while (top) fb -> sputc(buf[top--]);
fb -> sputc('\n');
}
}

int main() {
std::ios::sync_with_stdio(false);
cout.tie(NULL);
return 0;
}

图论

SPFA

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void spfa(int x) {
head = 0; tail = 1;
queue[tail] = x;
memset(vis, false, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
dis[x] = 0; vis[x] = true;
while (head++ < tail) {
int tn = queue[head];
vis[tn] = false;
for (int i = lin[tn], y; i; i = edge[i].ne)
if (dis[y = edge[i].y] > dis[tn] + edge[i].v){
dis[y] = dis[tn] + edge[i].v;
if (!vis[y]) {
vis[y] = true;
queue[++tail] = y;
}
}
}
}

dijkstra(堆优化)

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using std::vector;
using std::greater;
using std::make_pair;
typedef std::pair<int, int> pii;
typedef std::priority_queue<pii, vector<pii>, greater<pii> > priority_queue;
void dijkstra(int x) {
priority_queue queue;
memset(dis, 0x3f, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[x] = 0;
queue.push(make_pair(dis[x], x));
while (!queue.empty()) {
pii tmp = queue.top();
queue.pop();
int tn = tmp.second;
if (vis[tn]) continue;
vis[tn] = true;
for (int i = lin[x], y; i; i = edge[i].ne)
if (dis[y = edge[i].y] > dis[tn] + edge[i].v) {
dis[y] = dis[tn] + edge[i].v;
queue.push(make_pair(dis[y], y));
}
}
}

tarjan(割点)

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void tarjan(int x, int par) {
dfn[x] = low[x] = ++id;
int son = 0;
for (int i = lin[x], y; i; i = edge[i].ne) {
if ((y = edge[i].y) == par) continue;
if (!dfn[y]) {
tarjan(y, x);
if (low[y] < low[x]) low[x] = low[y];
if (dfn[x] <= low[y]) son++;
}
else if (dfn[y] < low[x]) low[x] = dfn[y];
}
if (son >= 2 || (par && son == 1)) iscut[x] = true;
}

tarjan(割边)

代码
1
2
3
4
5
6
7
8
9
10
11
12
void tarjan(int x, int par) {
dfn[x] = low[x] = ++id;
for (int i = lin[x]; i; i = edge[i].ne) {
if (i == par) continue;
if (!dfn[y = edge[i].y]) {
tarjan(y, rev[i]);
if (low[y] < low[x]) low[x] = low[y];
}
else if (dfn[y] < low[x]) low[x] = dfn[y];
}
if (dfn[x] == low[x]) isbridge[par] = isbridge[rev[par]] = true;
}

tarjan 求出割边后求边双连通分量

代码
1
2
3
4
5
6
7
8
void getbcc(int x) {
bel[x] = tot;
size[tot]++;
for (int i = lin[x], y; i; i = edge[i].ne) {
if (isbridge[i] || bel[y = edge[i].y]) continue;
getbcc(y);
}
}

tarjan(强连通分量)

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void tarjan(int x) {
dfn[x] = low[x] = ++ind;
vis[stack[++top] = x] = true;
for (int i = lin[x], y; i; i = edge[i].ne) {
if (!dfn[y = edge[i].y]) {
tarjan(y);
if (low[y] < low[x]) low[x] = low[y]
}
else if (vis[y] && dfn[y] < low[x]) low[x] = dfn[y];
}
if (dfn[x] == low[x]) {
tot++;
int k;
do {
k = stack[top--];
size[tot]++;
bel[k] = tot;
} while (k != x);
}
}

kruskal

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int getfather(int x) {
int anc = x, tmp;
while (father[anc] != anc) anc = father[anc];
while (x != anc) {
tmp = father[x];
father[x] = anc;
x = tmp;
}
return anc;
}

inline bool cmp(node a, node b) {
return a.v < b.v;
}

int kruskal() {
int ans = 0;
std::sort(edge + 1, edge + 1 + m, cmp);
for (int i = 1; i <= m; i++) {
int x = getfather(edge[i].x), y = getfather(edge[i].y);
if (x != y) {
father[x] = y;
ans += edge[i].v;
}
}
return ans;
}