noip 模板复习计划

三分法

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N = 50;

int n;
ld l, r, a[N];

ld get(ld x) {
	ld res = 0;
	for(int i = n ; i >= 0 ; -- i) {
		res = res * x + a[i];
	}
	return res;
}

int main() {
	cin >> n >> l >> r;
	for(int i = n ; i >= 0 ; -- i) cin >> a[i];
	for(int i = 1 ; i <= 100 ; ++ i) {
		ld len = (r - l) / 3;
		ld ml = l + len, mr = l + len * 2;
		if(get(ml) > get(mr)) {
			r = mr;
		} else {
			l = ml;
		}
	}
	cout << fixed << setprecision(5) << l << endl;
}

负环

#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 2010, M = 6010, inf = 0x3f3f3f3f;
int n, m;
int head[N], rest[M], w[M], to[M], tot;
void add(int u, int v, int wi) {
    to[++ tot] = v, w[tot] = wi, rest[tot] = head[u], head[u] = tot;
}
int dis[N], cnt[N], inq[N];

void sol() {
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++ i) {
        inq[i] = 0;
        head[i] = 0;
        dis[i] = inf;
        cnt[i] = 0;
    }
    tot = 0;
    for(int i = 1, u, v, w ; i <= m ; ++ i) {
        cin >> u >> v >> w;
        if(w < 0) add(u, v, w);
        else add(u, v, w), add(v, u, w);
    }
    queue<int> q;
    q.push(1), dis[1] = 0, inq[1] = 1;
    while(q.size()) {
        int u = q.front(); q.pop();
        inq[u] = 0;
        if(++ cnt[u] > n) {
            puts("YE5");
            return ;
        }
        for(int i = head[u] ; i ; i = rest[i]) {
            int v = to[i], w = :: w[i];
            if(dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if(!inq[v]) {
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
    puts("N0");
}

int main() {
    int T; cin >> T;
    while(T --) sol();
}

ST表

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N], f[N][21];
int lg[N];

void init() {
    lg[0] = -1;
    for(int i = 1 ; i <= n ; ++ i) lg[i] = lg[i >> 1] + 1;
    for(int i = 1 ; i <= n ; ++ i) f[i][0] = a[i];
    for(int j = 1 ; j <= 20 ; ++ j)
        for(int i = 1 ; i + (1 << j) - 1 <= n ; ++ i)	
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

int sol(int l, int r) {
    int k = lg[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1 ; i <= n ; ++ i) scanf("%d", &a[i]);
    init();
    for(int i = 1, l, r ; i <= m ; ++ i) {
        scanf("%d%d", &l, &r);
        printf("%d\n", sol(l, r));
    }
}

manacher算法

#include <bits/stdc++.h>
using namespace std;
const int N = 22000000 + 10;

int n, rig[N];
char str[N];

int main() {
    scanf("%s", str + 1), n = strlen(str + 1);
    for(int i = n ; i ; -- i) {
        str[2 * i] = str[i];
    }
    for(int i = 1 ; i <= 2 * n + 1 ; i += 2) {
        str[i] = '#';
    }
    n = 2 * n + 1;
    for(int i = 1, pos = -1, mxr = -1 ; i <= n ; ++ i) {
        rig[i] = i > mxr ? 1 : min(mxr - i, rig[2 * pos - i]);
        while(i - rig[i] >= 1 && i + rig[i] <= n && str[i - rig[i]] == str[i + rig[i]]) ++ rig[i];
        if(i + rig[i] - 1 > mxr) {
            mxr = i + rig[i] - 1;
            pos = i;
        }
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; ++ i) {
        ans = max(ans, rig[i] - 1);
    }
    printf("%d\n", ans); 
}

线性基

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 60;
int n; ll a[N];

int main() {
	scanf("%d", &n);
	for(int i = 1 ; i <= n ; ++ i) {
		ll x; scanf("%lld", &x);
		for(int j = 50 ; ~ j ; -- j) {
			if((x >> j) & 1) {
				if(!a[j]) {
					a[j] = x;
					break;
				}
				x ^= a[j];
			}
		}
	}
	ll ans = 0;
	for(int i = 50 ; ~ i ; -- i)
		if((ans ^ a[i]) > ans)
			ans ^= a[i];
	printf("%lld\n", ans);
}

双排列的最长公共子序列

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
int n, a[N], b[N], c[N], e[N], d[N], f[N], ans;
void add(int x, int y) {
	for( ; x <= n ; x += x & -x)
		d[x] = max(d[x], y);
}
int ask(int x) {
	int r = 0;
	for( ; x ; x -= x & -x)
		r = max(r, d[x]);
	return r;
}

int main() {
	scanf("%d", &n);
	for(int i = 1 ; i <= n ; ++ i) scanf("%d", &a[i]);
	for(int i = 1 ; i <= n ; ++ i) scanf("%d", &b[i]), e[b[i]] = i;
	for(int i = 1 ; i <= n ; ++ i) c[i] = e[a[i]];
	for(int i = 1 ; i <= n ; ++ i) {
		ans = max(ans, f[i] = ask(c[i]) + 1);
		add(c[i], f[i]);
	}
	printf("%d\n", ans);
}

最近公共祖先（LCA）

#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 10;
int n, m, root;
int head[N], rest[N * 2], to[N * 2], tot;
void add(int u, int v) {
    to[++ tot] = v, rest[tot] = head[u], head[u] = tot;
}
int fa[N][21], dep[N];
void dfs(int u) {
    dep[u] = dep[fa[u][0]] + 1;
    for(int i = 1 ; i <= 20 ; ++ i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(v == fa[u][0]) continue;
        fa[v][0] = u;
        dfs(v);
    }
}
int getlca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 20 ; ~ i ; -- i)
        if(dep[fa[u][i]] >= dep[v])
            u = fa[u][i];
    if(u == v) return u;
    for(int i = 20 ; ~ i ; -- i)
        if(fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

int main() {
    scanf("%d%d%d", &n, &m, &root);
    for(int i = 1, u, v ; i < n ; ++ i) {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs(root);
    for(int i = 1, u, v ; i <= m ; ++ i) {
        scanf("%d%d", &u, &v);
        printf("%d\n", getlca(u, v));
    }
}

缩点

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
vector<int> G[N], g[N];
int n, m, a[N];

int dfn[N], low[N], clk, sta[N], top, ins[N], cnt, sum[N], bel[N];

void dfs(int u) {
	sta[++ top] = u, ins[u] = 1;
	dfn[u] = low[u] = ++ clk;
	for(int i = 0 ; i < G[u].size() ; ++ i) {
		int v = G[u][i];
		if(!dfn[v]) {
			dfs(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; ++ cnt;
		do {
			v = sta[top --]; ins[v] = 0;
			bel[v] = cnt;
			sum[cnt] += a[v];
		} while(v != u);
	}
}

int f[N];

int go(int u) {
	if(f[u] != -1) return f[u];
	f[u] = 0;
	for(int i = 0 ; i < g[u].size() ; ++ i) {
		int v = g[u][i];
		f[u] = max(f[u], go(v));
	}
	return f[u] += sum[u];
}

int main() {
	memset(f, -1, sizeof f);
	scanf("%d%d", &n, &m);
	for(int i = 1 ; i <= n ; ++ i) scanf("%d", &a[i]);
	for(int i = 1, u, v ; i <= m ; ++ i) {
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
	}
	for(int i = 1 ; i <= n ; ++ i)
		if(!dfn[i])
			dfs(i);
	for(int u = 1 ; u <= n ; ++ u) {
		for(int i = 0 ; i < G[u].size() ; ++ i) {
			int v = G[u][i];
			int x = bel[u], y = bel[v];
			if(x != y) {
				g[x].push_back(y);
			}
		}
	}
	int ans = 0;
	for(int i = 1 ; i <= cnt ; ++ i)
		ans = max(ans, go(i));
	printf("%d\n", ans);
}

文艺平衡树

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;

typedef pair<int, int> pii;
int root, sz[N], ch[N][2], tot, val[N], fix[N], rev[N];

int nd(int x) {
	return val[++ tot] = x, sz[tot] = 1, tot;
}

void push(int x) {
	if(x && rev[x]) {
		swap(ch[x][0], ch[x][1]);
		rev[ch[x][0]] ^= 1, rev[ch[x][1]] ^= 1;
		rev[x] = 0;
	}
}

int up(int x) {
	return sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1, x;
}

int merge(int x, int y) {
	push(x), push(y);
	if(!x || !y) return x | y;
	if(fix[x] < fix[y]) {
		ch[x][1] = merge(ch[x][1], y);
		return up(x);
	} else {
		ch[y][0] = merge(x, ch[y][0]);
		return up(y);
	}
}

pii split(int x, int k) {
	pii r;
	if(x) {
		push(x);
		if(sz[ch[x][0]] >= k) {
			r = split(ch[x][0], k);
			ch[x][0] = r.second, r.second = x;
		} else {
			r = split(ch[x][1], k - sz[ch[x][0]] - 1);
			ch[x][1] = r.first, r.first = x;
		}
		up(x);
	}
	return r;
}

void dfs(int u) {
	if(!u) return ;
	push(u);
	dfs(ch[u][0]);
	printf("%d ", val[u]);
	dfs(ch[u][1]);
}

int main() {
	srand((unsigned long long) new char);
	int n, m; scanf("%d%d", &n, &m);
	for(int i = 1 ; i <= n ; ++ i) fix[i] = i; random_shuffle(fix + 1, fix + 1 + n);
	for(int i = 1 ; i <= n ; ++ i) {
		root = merge(root, nd(i));
	}
	for(int i = 1, l, r ; i <= m ; ++ i) {
		scanf("%d%d", &l, &r);
		pii x = split(root, r);
		pii y = split(x.first, l - 1);
		rev[y.second] ^= 1;
		root = merge(merge(y.first, y.second), x.second);
	}
	dfs(root);
}

最小生成树

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
struct E {
	int u, v, w;
} e[N];
bool operator < (E a, E b) {
	return a.w < b.w;
}
long long ans;
int fa[N];
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]); }
int main() {
	int n, m; scanf("%d%d", &n, &m);
	for(int i = 1 ; i <= m ; ++ i)
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	sort(e + 1, e + 1 + m);
	for(int i = 1 ; i <= n ; ++ i) fa[i] = i;
	for(int i = 1 ; i <= m ; ++ i) {
		int u = e[i].u, v = e[i].v, w = e[i].w;
		if(get(u) != get(v)) {
			fa[get(u)] = get(v);
			ans += w;
		}
	}
	for(int i = 1 ; i <= n ; ++ i)
		if(get(i) != get(1))
			return puts("orz"), 0;
	printf("%lld\n", ans);
}

线性筛素数

#include <bits/stdc++.h>
using namespace std;
const int N = 10000000 + 10;
int pri[N], tot; bool vis[N];

int main() {
	int n, m; scanf("%d%d", &n, &m);
	vis[1] = 1;
	for(int i = 2 ; i <= n ; ++ i) {
		if(!vis[i]) pri[++ tot] = i;
		for(int j = 1 ; j <= tot && i * pri[j] <= n ; ++ j) {
			vis[i * pri[j]] = 1;
			if(i % pri[j] == 0) break;
		}
	}
	for(int i = 1, x ; i <= m ; ++ i) {
		scanf("%d", &x);
		puts(vis[x] ? "No" : "Yes");
	}
}

线段树 1

#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 100000 * 10 + 10;

ll tag[N], sum[N];
int n, m;


#define lc (id << 1)
#define rc (id << 1 | 1)
void build(int id, int l, int r) {
    int mid = (l + r) >> 1;
    if(l == r) {
        scanf("%lld", &sum[id]);
    } else {
        build(lc, l, mid), build(rc, mid + 1, r);
        sum[id] = sum[lc] + sum[rc]; 
    }
} 

void push(int id, int l, int r) {
    if(tag[id]) {
        sum[id] += tag[id] * (r - l + 1);
        tag[lc] += tag[id], tag[rc] += tag[id];
        tag[id] = 0;
    }
}

void up(int id, int l, int r) {
    int mid = (l + r) >> 1;
    push(lc, l, mid), push(rc, mid + 1, r);
    sum[id] = sum[lc] + sum[rc];
}

void modify(int id, int l, int r, int ql, int qr, ll x) {
    int mid = (l + r) >> 1;
    push(id, l, r);
    if(ql <= l && r <= qr) {
        tag[id] += x;
        return ;
    } else if(qr <= mid) {
        modify(lc, l, mid, ql, qr, x);
    } else if(ql >= mid + 1) {
        modify(rc, mid + 1, r, ql, qr, x);
    } else {
        modify(lc, l, mid, ql, mid, x);
        modify(rc, mid + 1, r, mid + 1, qr, x);
    }
    up(id, l, r);
}

ll ask(int id, int l, int r, int ql, int qr) {
    int mid = (l + r) >> 1;
    push(id, l, r);
    if(ql <= l && r <= qr) {
        return sum[id];
    } else if(qr <= mid) {
        return ask(lc, l, mid, ql, qr);
    } else if(ql >= mid + 1) {
        return ask(rc, mid + 1, r, ql, qr);
    } else {
        return ask(lc, l, mid, ql, mid) + ask(rc, mid + 1, r, mid + 1, qr);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    for(int i = 1, op, l, r ; i <= m ; ++ i) {
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1) {
            ll k; scanf("%lld", &k);
            modify(1, 1, n, l, r, k);
        } else {
            printf("%lld\n", ask(1, 1, n, l, r)); 
        }
    }
}

二分图匹配

#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 10;
int mat[N], n, m, e;
int a[N][N], T, vis[N], ans;

int dfs(int u) {
	for(int v = 1 ; v <= m ; ++ v) {
		if(a[u][v] && vis[v] != T) {
			vis[v] = T;
			if(!mat[v] || dfs(mat[v])) {
				mat[v] = u;
				return 1;
			}
		}
	}
	return 0;
}

int main() {
	scanf("%d%d%d", &n, &m, &e);
	for(int i = 1, u, v ; i <= e ; ++ i) {
		scanf("%d%d", &u, &v);
		if(v > m) continue;
		a[u][v] = 1;
	}
	for(int i = 1 ; i <= n ; ++ i) {
		++ T;
		if(dfs(i)) {
			++ ans;
		}
	}
	printf("%d\n", ans);
}

割点（割顶）

#include <bits/stdc++.h>
using namespace std;
const int N = 20000 + 10, M = 200000 + 10;
int n, m;
int head[N], rest[M], to[M], tot = 1, ans;
void add(int u, int v) {
    to[++ tot] = v, rest[tot] = head[u], head[u] = tot;
}

int dfn[N], low[N], clk, cut[N], root;
void dfs(int u, int fr) {
    dfn[u] = low[u] = ++ clk;
    int tot = 0;
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(i == fr) continue;
        if(!dfn[v]) {
            dfs(v, i);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                ++ tot;
                if(tot > 1 || u != root) {
                    cut[u] = 1;
                }
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    ans += cut[u];
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v ; i <= m ; ++ i) {
        scanf("%d%d", &u, &v);
        if(u == v) continue;
        add(u, v), add(v, u);
    }
    for(int i = 1 ; i <= n ; ++ i)
        if(!dfn[i])
            dfs(root = i, 0);
    printf("%d\n", ans);
    for(int i = 1 ; i <= n ; ++ i)
        if(cut[i])
            printf("%d ", i);
}

卢卡斯定理

#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 2e5 + 10;
ll n, m, p, fac[N], invfac[N];
ll pw(ll a, ll b) {
	ll r = 1;
	for( ; b ; b >>= 1, a = a * a % p)
		if(b & 1)
			r = r * a % p;
	return r;
}

ll C(ll n, ll m) {
	if(n < m) return 0;
	if(n < p) return fac[n] * invfac[m] % p * invfac[n - m] % p;
	return C(n / p, m / p) * C(n % p, m % p) % p;
}

void sol() {
	cin >> n >> m >> p;
	if(p == 1) {
		cout << 0 << endl;
		return ;
	}
	fac[0] = invfac[0] = 1;
	for(int i = 1 ; i < p ; ++ i) fac[i] = fac[i - 1] * i % p;
	invfac[p - 1] = pw(fac[p - 1], p - 2);
	for(int i = p - 2 ; i >= 1 ; -- i) invfac[i] = invfac[i + 1] * (i + 1) % p;
	cout << C(n + m, m) << endl;
}

int main() {
	int T; cin >> T;
	while(T --) sol();
}

高斯消元法

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N = 110;
int n; ld a[N][N];

int main() {
	ios :: sync_with_stdio(0);
	cin >> n;
	for(int i = 1 ; i <= n ; ++ i)
		for(int j = 1 ; j <= n + 1 ; ++ j)
			cin >> a[i][j];
	for(int i = 1 ; i <= n ; ++ i) {
		int ch = i;
		for(int j = i ; j <= n ; ++ j)
			if(fabs(a[j][i]) > fabs(a[ch][i]))
				ch = j;
		if(fabs(a[ch][i]) < 1e-7) {
			cout << "No Solution" << endl;
			return 0;
		}
		for(int j = i ; j <= n + 1 ; ++ j)
			swap(a[i][j], a[ch][j]);
		for(int j = i + 1 ; j <= n ; ++ j) {
			ld t = a[j][i] / a[i][i];
			for(int k = i ; k <= n + 1 ; ++ k) {
				a[j][k] -= a[i][k] * t;
			}
		}
	}
	
	for(int i = n ; i >= 1 ; -- i) {
		a[i][n + 1] /= a[i][i];
		for(int j = i - 1 ; j >= 1 ; -- j) {
			a[j][n + 1] -= a[j][i] * a[i][n + 1];
		}
	}
	
	for(int i = 1 ; i <= n ; ++ i) {
		cout << fixed << setprecision(2) << a[i][n + 1] << endl;
	}
}

网络最大流

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 2e5 + 10, inf = 0x3f3f3f3f;
int head[N], rest[M], to[M], w[M], tot = 1;

void add(int u, int v, int w) {
	to[++ tot] = v, :: w[tot] = w, rest[tot] = head[u], head[u] = tot;
}

int n, m, s, t;

int dis[N];

bool bfs() {
	for(int i = 1 ; i <= n ; ++ i) dis[i] = -1;
	dis[s] = 1;
	queue<int> q; q.push(s);
	while(q.size()) {
		int u = q.front(); q.pop();
		for(int i = head[u] ; i ; i = rest[i]) {
			int v = to[i];
			if(w[i] && dis[v] == -1) {
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
	return dis[t] != -1;
}

int cur[N];
int dfs(int u, int flow) {
	int use = 0;
	if(u == t || !flow) return flow;
	for(int &i = cur[u] ; i ; i = rest[i]) {
		int v = to[i];
		if(dis[v] == dis[u] + 1) {
			int a = dfs(v, min(flow - use, w[i]));
			use += a;
			w[i] -= a;
			w[i ^ 1] += a;
			if(use == flow) break;
		}
	}
	if(!use) dis[u] = -1;
	return use;
}

int main() {
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for(int i = 1, u, v, w ; i <= m ; ++ i) {
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w), add(v, u, 0);
	}
	int ans = 0;
	while(bfs()) {
		for(int i = 1 ; i <= n ; ++ i) cur[i] = head[i];
		ans += dfs(s, inf);
	}
	printf("%d\n", ans);
}

最小费用最大流

#include <bits/stdc++.h>
using namespace std;
const int N = 5010, M = 1e5 + 10, inf = 0x3f3f3f3f;
int head[N], rest[M], from[M], to[M], w[M], co[M], tot = 1;
void add(int u, int v, int w, int co) {
    from[++ tot] = u, to[tot] = v, :: w[tot] = w, :: co[tot] = co, rest[tot] = head[u], head[u] = tot;
}
int n, m, s, t;

int dis[N], inq[N], pre[N];
bool spfa() {
    for(int i = 1 ; i <= n ; ++ i) dis[i] = inf, pre[i] = 0;
    queue<int> q;
    q.push(s), inq[s] = 1, dis[s] = 0;
    while(q.size()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for(int i = head[u] ; i ; i = rest[i]) {
            int v = to[i], co = :: co[i];
            if(w[i] && dis[v] > dis[u] + co) {
                dis[v] = dis[u] + co;
                pre[v] = i;
                if(!inq[v]) {
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
    return dis[t] != inf;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i = 1, u, v, w, co ; i <= m ; ++ i) {
        scanf("%d%d%d%d", &u, &v, &w, &co);
        add(u, v, w, co), add(v, u, 0, -co);
    }
    int mxf = 0, sum = 0;
    while(spfa()) {
        int mn = inf;
        for(int i = pre[t] ; i ; i = pre[from[i]]) {
            mn = min(mn, w[i]);
        }
        for(int i = pre[t] ; i ; i = pre[from[i]]) {
            w[i] -= mn;
            w[i ^ 1] += mn;
        }
        mxf += mn;
        sum += mn * dis[t];
    }
    printf("%d %d\n", mxf, sum);
}

floyd 最小环

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10, inf = 0x3f3f3f3f;
int n, m, a[N][N], b[N][N];

void sol() {
	memset(a, 0x3f, sizeof a);
	memset(b, 0x3f, sizeof b);
	for(int i = 1, u, v, w ; i <= m ; ++ i) {
		scanf("%d%d%d", &u, &v, &w);
		a[v][u] = a[u][v] = min(a[u][v], w);
		b[v][u] = b[u][v] = min(b[u][v], w);
	}
	int ans = inf;
	for(int k = 1 ; k <= n ; ++ k) {
		for(int i = 1 ; i <= k ; ++ i) {
			for(int j = i + 1 ; j <= k ; ++ j) {
				if(b[i][k] != inf && b[k][j] != inf && a[i][j] != inf) {
					ans = min(ans, b[i][k] + b[k][j] + a[i][j]);
				}
			}
		}
		for(int i = 1 ; i <= n ; ++ i) {
			for(int j = 1 ; j <= n ; ++ j) {
				a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
			}
		}
	}
	if(ans == inf) puts("It's impossible.");
	else printf("%d\n", ans);
}
int main() {
	while(scanf("%d%d", &n, &m) == 2) sol();
}

KMP字符串匹配

#include <bits/stdc++.h>
using namespace std;
const int N = 2000000 + 10;
char s[N], t[N]; int n;
int nxt[N]; 

int main() {
	scanf("%s%s", s + 1, t + 1);
	int lens = strlen(s + 1);
	int lent = strlen(t + 1);
	strcat(t + 1, ".");
	strcat(t + 1, s + 1);
	n = strlen(t + 1);
	for(int i = 2, j = 0 ; i <= n ; ++ i) {
		while(j && t[i] != t[j + 1]) j = nxt[j];
		if(t[i] == t[j + 1]) ++ j;
		nxt[i] = j;
		if(nxt[i] == lent) {
			printf("%d\n", i - lent - 1 - lent + 1);
		}
	}
	for(int i = 1 ; i <= lent ; ++ i)
		printf("%d ", nxt[i]); 
} 

AC自动机（简单版）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n; char s[N];
int ch[N][26], tot, val[N], fail[N];

int main() {
    scanf("%d", &n);
    for(int i = 1 ; i <= n ; ++ i) {
        scanf("%s", s + 1);
        int x = 0; for(int j = 1 ; s[j] ; ++ j) {
            int c = s[j] - 'a';
            if(!ch[x][c]) ch[x][c] = ++ tot;
            x = ch[x][c];
        }
        val[x] ++;
    }
    queue<int> q;
    for(int i = 0 ; i < 26 ; ++ i)
        if(ch[0][i])
            q.push(ch[0][i]), fail[ch[0][i]] = 0;
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int i = 0 ; i < 26 ; ++ i) {
            if(ch[u][i]) {
                fail[ch[u][i]] = ch[fail[u]][i];
                q.push(ch[u][i]);
            } else {
                ch[u][i] = ch[fail[u]][i];
            }
        }
    }
    scanf("%s", s + 1);
    int ans = 0;
    for(int x = 0, i = 1 ; s[i] ; ++ i) {
        int c = s[i] - 'a';
        x = ch[x][c];
        for(int j = x ; j && val[j] != -1 ; j = fail[j]) {
            ans += val[j];
            val[j] = -1;
        }
    }
    printf("%d\n", ans);
}