2013-team5/常用模板
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
关键词： 后缀数组 AC自动机 AC+dp 分数规划 二分图最小权 二分图最大权 2-sat 最大流 最短路径（负环判定）
最小生成树(kruskal、并查集) 最小生成树prim stl优先队列的简单用法 二分图最大匹配 康托展开 最小费用(最大)流 日期
Treap Splay 辛普森 因子分解
后缀数组
const int N = 40005;
int sa[N], rk[N], height[N];
int wa[N], wb[N], wv[N], wts[N];
inline bool cmp(int *r, int a, int b, int len) {
return (r[a]==r[b]) && (r[a+len]==r[b+len]);
}
void sortSA(char *r, int *sa, int n, int m){
int i, j, p, *x = wa, *y = wb, *t;
for(i = 0; i < m; i++)
wts[i] = 0;
for(i = 0; i < n; i++)
wts[x[i]=r[i]]++;
for(i = 1; i < m; i++)
wts[i] += wts[i-1];
for(i = n-1; i >= 0; i--)
sa[--wts[x[i]]] = i;
for(j = p = 1; p < n; j <<= 1, m = p){
for(p=0, i=n-j; i < n; i++)
y[p++] = i;
for(i = 0; i < n; i++){
if(sa[i] >= j)
y[p++] = sa[i] - j;
}
for(i = 0; i < m; i++)
wts[i] = 0;
for(i = 0; i < n; i++)
wts[wv[i]=x[y[i]]]++;
for(i = 1; i < m; i++)
wts[i] += wts[i-1];
for(i = n-1; i >= 0; i--)
sa[--wts[wv[i]]] = y[i];
for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1; i < n; i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j) ? p-1:p++;
}
}
void calHeight(char *r, int *sa, int n){
int i, j, k = 0;
for(i = 1; i <= n; i++) rk[sa[i]] = i;
for(i = 0; i < n; i++){
for(k? k--:0, j=sa[rk[i]-1]; r[i+k]==r[j+k]; k++);
height[rk[i]] = k;
}
}
AC自动机
struct node {
int ct;
node *pre, *next[26];
void init() {
ct = 0;
pre = 0;
memset(next, 0, sizeof(next));
}
};
int cnt; //节点总数
node *root, trie[500010];
node *queue[500010];
void insertStr(node *root, char *str) {
int index, len = strlen(str);
for(int i = 0; i < len; i++) {
index = str[i]-'a';
if(root->next[index] == 0) {
root->next[index] = &trie[++cnt];
root->next[index]->init();
}
root = root->next[index];
}
root->ct++;
}
void buildAC() {
int head, tail;
node *u, tmp;
queue[0] = root;
root->pre = root;
head = tail = 0;
while(head <= tail) {
u = queue[head++];
for(int i = 0; i < 26; i++) {
if(u->next[i] == 0) {
if(u == root) u->next[i] = root;
else u->next[i] = u->pre->next[i];
}
else {
if(u == root) u->next[i]->pre = root;
else u->next[i]->pre = u->pre->next[i];
queue[++tail] = u->next[i];
}
}
}
}
分数规划
（1） 一般分数规划的解法
简单总结一下解分数规划的一般步骤吧：
1.对于最小化目标函数r = ax/bx，则构造函数g(r)=min{ax - r*bx}
对于最大化目标函数r = ax/bx，等价于最小化目标函数bx/ax，因此同上。
2.由各种大科学家大神们证明得结论T_T：
(1)g(r)是单调减函数(有些离散情况下也有可能是单调不增加函数)，即随r的增加而减小。
(2)若r是最优解，则g(r)==0。。
3.建立模型二分r求解。
二分图最小权匹配
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
using namespace std;
const int N =105;
const int M =10005;
const int inf =0x1fffffff;
int n, m, tot, lx[N], ly[N], match[N], h[N], v[M], w[M], nxt[M];
bool visx[N], visy[N];
int lack;
void add(int a, int b, int c)
{
v[tot] = b;
w[tot] = c;
nxt[tot] = h[a];
h[a] = tot++;
}
bool find(int u)
{
int i, t;
visx[u] =true;
for(i = h[u]; i !=-1; i = nxt[i])
if(!visy[v[i]])
{
t = w[i] - lx[u] - ly[v[i]];
if(t ==0)
{
visy[v[i]] =true;
if(match[v[i]]==-1|| find(match[v[i]]))
{
match[v[i]] = u;
return true;
}
}
else if(t >0)
lack = min(lack, t);
}
return false;
}
int calMatch(int n) {
int ans = 0;
for(int i =1; i <= n; i++)
{
lx[i] = inf;
ly[i] =0;
for(int j = h[i]; j !=-1; j = nxt[j])
lx[i] = min(lx[i], w[j]);
}
memset(match, -1, sizeof(match));
for(int i =1; i <= n; i++)
{
memset(visx, false, sizeof(visx));
memset(visy, false, sizeof(visy));
lack = inf;
while(!find(i))
{
for(int j =1; j <= n; j++)
{
if(visx[j]) lx[j] += lack;
if(visy[j]) ly[j] -= lack;
}
memset(visx, false, sizeof(visx));
memset(visy, false, sizeof(visy));
}
}
ans = 0;
for(int i =1; i <= n; i++) ans = ans + lx[i] + ly[i];
return ans;
}
二分图最大权匹配
#include <iostream>
#include <cstdio>
#include <cstring>
usingnamespace std;
constint N =310;
constint inf =0x1fffffff;
int n, lx[N], ly[N], match[N], w[N][N];
bool visx[N], visy[N];
int lack;
int getNum()
{
char c;
int ans =0;
c = getchar();
while(c<'0'|| c>'9') c = getchar();
while(c>='0'&& c<='9')
{
ans = ans*10+c-'0';
c = getchar();
}
return ans;
}
bool find(int u)
{
int i, t;
visx[u] =true;
for(i =1; i <= n; i++)
if(!visy[i])
{
t = lx[u] + ly[i] - w[u][i];
if(t ==0)
{
visy[i] =true;
if(match[i]==-1|| find(match[i]))
{
match[i] = u;
returntrue;
}
}
elseif(t >0)
lack = min(lack, t);
}
returnfalse;
}
int main()
{
int i, j, ans;
while(scanf("%d", &n) != EOF)
{
for(i =1; i <= n; i++)
{
lx[i] = ly[i] =0;
for(j =1; j <= n; j++)
{
w[i][j] = getNum();
lx[i] = max(lx[i], w[i][j]);
}
}
memset(match, -1, sizeof(match));
for(i =1; i <= n; i++)
{
memset(visx, false, sizeof(visx));
memset(visy, false, sizeof(visy));
lack = inf;
while(!find(i))
{
for(j =1; j <= n; j++)
{
if(visx[j]) lx[j] -= lack;
if(visy[j]) ly[j] += lack;
}
memset(visx, false, sizeof(visx));
memset(visy, false, sizeof(visy));
}
}
ans =0;
for(i =1; i <= n; i++) ans = ans + lx[i] + ly[i];
printf("%d\n", ans);
}
return0;
}
2-SAT问题（判定+求解）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1010;
int n; //原图中共有2*n个相对的节点。
int ct, depth, top, index[N<<1], d[N<<1], low[N<<1], stack[N<<1];
bool instack[N<<1], map[N<<1][N<<1], g[N<<1][N<<1];
int tot, et[N<<1], color[N<<1], op[N<<1];
bool visit[N<<1];
void initData() { //初始化数据，根据题意建图，建好的初始图为map
........
}
void dfs(int u) { //tarjan求强连通分量，缩点
int i, x;
d[u] = low[u] = depth++;
stack[++top] = u;
instack[u] =true;
for(i = 0; i < n+n; i++)
if(map[u][i]) {
if(d[i] == -1) {
dfs(i);
low[u] = min(low[u], low[i]);
}
else {
if(instack[i])
low[u] = min(low[u], d[i]);
}
}
if(low[u] == d[u]) {
ct++;
while(top)
{
x = stack[top--];
instack[x] = false;
index[x] = ct;
if(x == u) break;
}
}
}
void buildNewGraph() { //根据缩点建立新图
int i, j;
memset(g, false, sizeof(g));
for(i = 0; i < n+n; i++)
for(j = 0; j < n+n; j++)
if(map[i][j])
g[index[i]][index[j]] = true;
for(i = 1; i <= ct; i++)
for(j = i+1; j <= ct; j++)
swap(g[i][j], g[j][i]); //将新图中的边反向
for(i = 0; i < n; i++) { //根据原图的矛盾节点确定新图的矛盾节点
op[index[i]] = index[i+n];
op[index[i+n]] = index[i];
}
}
void transDfs(int u) {
int i;
visit[u] =true;
for(i = 1; i <= ct; i++)
if(!visit[i] && g[u][i])
transDfs(i);
et[++tot] = u;
}
void colorDfs(int u) {
int i;
color[u] = 0;
for(i = 1; i <= ct; i++)
if(color[i]==-1 && g[u][i])
colorDfs(i);
}
void generateAns() {
int i;
memset(visit, false, sizeof(visit));
tot = 0;
//拓扑排序
for(i = 1; i <= ct; i++)
if(!visit[i])
transDfs(i);
memset(color, -1, sizeof(color));
for(i = ct; i > 0; i--)
if(color[et[i]] == -1) {
color[et[i]] = 1;
//选择第一个未着色的顶点x, 把x染成红色1, 并把与之矛盾的节点y及其所有子孙节点染成蓝色0。
colorDfs(op[et[i]]);
}
}
void solve() {
int i;
depth = top = ct =0;
memset(d, -1, sizeof(d));
memset(instack, false, sizeof(instack));
for(i = 0; i < n+n; i++)
if(d[i] == -1)
dfs(i);
for(i = 0; i < n; i++)
if(index[i] == index[i+n])
break;
if(i < n) printf("NO\n");
else {
printf("YES\n");
buildNewGraph();
generateAns();
//printAns();
}
}
int main()
{
initData();
solve();
return 0;
}
最大流-dinic
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
const int Maxn = 20005;
const int Maxm = (200005<<1)+(Maxn<<1);
const int inf = 0x1fffffff;
int n, m, queue[Maxn], lab[Maxn];
int tot, h[Maxn], nxt[Maxm<<1], v[Maxm<<1], res[Maxm<<1];
void addEdge(int a, int b, int c) {
v[tot] = b; res[tot] = c; nxt[tot] = h[a]; h[a] = tot++;
v[tot] = a; res[tot] = 0; nxt[tot] = h[b]; h[b] = tot++;
}
bool bfs(int s, int t) {
int head, tail, u;
memset(lab, -1, sizeof(lab));
lab[s] = head = tail =0;
queue[0] = s;
while(head <= tail) {
u = queue[head++];
for(int i = h[u]; i != -1; i = nxt[i])
if(res[i]>0 && lab[v[i]]==-1) {
lab[v[i]] = lab[u] +1;
queue[++tail] = v[i];
}
}
if(lab[t] != -1) return true;
else return false;
}
int dinicDfs(int delta, int u, int t) {
int sum =0, tmp;
if(u == t) return delta;
else {
for(int i = h[u]; i != -1; i = nxt[i])
if(lab[v[i]]==lab[u]+1 && res[i]>0) {
tmp = dinicDfs(min(delta, res[i]), v[i], t);
sum += tmp;
delta -= tmp;
res[i] -= tmp;
res[i^1] += tmp;
if(delta == 0) break;
}
if(sum == 0) lab[u] = -1;
return sum;
}
}
int maxFlow(int s, int t) {
int ans =0;
while(bfs(s, t))
ans += dinicDfs(inf, s, t);
return ans;
}
int main()
{
int a, b, c, s, t;
freopen("data.txt", "r", stdin);
while(scanf("%d%d", &n, &m) != EOF) {
s = 0; t = n+1;
tot = 0;
for(int i = 0; i <= t; i++) h[i] = -1;
for(int i = 1; i <= n; i++) {
scanf("%d%d", &a, &b);
addEdge(s, i, a); addEdge(i, t, b);
}
while(m--) {
scanf("%d%d%d", &a, &b, &c);
addEdge(a, b, c); addEdge(b, a, c);
}
int ans = maxFlow(s, t);
cout << ans << endl;
}
return 0;
}
最短路径（spfa判负环）
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 550;
const int M = 3000<<1;
int Case, n, m, w;
int tot, h[N], nxt[M], c[M], v[M];
int used[N], dis[N];
bool visit[N];
void add(int s, int t, int e) {
v[tot] = t; c[tot] = e;
nxt[tot] = h[s]; h[s] = tot++;
}
bool spfa(int s) {
int u;
queue <int> q; while(!q.empty()) q.pop();
memset(visit, false, sizeof(visit));
memset(used, 0, sizeof(used));
for(int i = 1; i <= n; i++) dis[i] = 0x1fffffff; dis[0] = 0;
used[0] = 1;
q.push(s);
while(!q.empty()) {
u = q.front(); q.pop();
visit[u] = false;
for(int p = h[u]; p != -1; p = nxt[p]) {
if(dis[v[p]] > dis[u] + c[p]) {
dis[v[p]] = dis[u] + c[p];
if(!visit[v[p]]) {
visit[v[p]] = true;
q.push(v[p]);
used[v[p]]++;
if(used[v[p]] >= n) return true;
}
}
}
}
return false;
}
int main() {
int s, t, e;
scanf("%d", &Case);
while(Case--) {
scanf("%d%d%d", &n, &m, &w);
memset(h, -1, sizeof(h)); tot = 0;
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &s, &t, &e);
add(s, t, e);
add(t, s, e);
}
for(int i = 0; i < w; i++) {
scanf("%d%d%d", &s, &t, &e);
add(s, t, -e);
}
for(int i = 1; i <= n; i++) add(0, i, 0);
if(spfa(0)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
最小生成树 (kruskal、并查集)
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 200010;
struct node {
int x, y, cost;
}e[N];
int n, m, father[N];
bool cmp(const node &a, const node &b) {
return a.cost < b.cost;
}
int getFather(int u) {
if(father[u] != u) father[u] = getFather(father[u]);
return father[u];
}
int kruskal() {
int fa, fb, sum = 0;
for(int i = 0; i < n; i++) father[i] = i;
sort(e, e+m, cmp);
for(int i = 0; i < m; i++) {
fa = getFather(e[i].x); fb = getFather(e[i].y);
if(fa == fb) continue;
else {
father[fb] = father[fa];
sum += e[i].cost;
}
}
return sum;
}
int main() {
int tot;
freopen("data.in", "r", stdin);
while(scanf("%d%d", &n, &m) != EOF) {
if(n==0 && m==0) break;
tot = 0;
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].cost);
tot += e[i].cost;
}
int ans = tot-kruskal();
printf("%d\n", ans);
}
return 0;
}
最小生成树prim
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 105;
int Case, n;
bool visit[N];
double x[N], y[N], dis[N], g[N][N];
double Cal(int a, int b) {
double tx=x[a]-x[b], ty=y[a]-y[b];
return sqrt(tx*tx + ty*ty);
}
double prim() {
double tot = 0.0, min;
int v;
for(int i = 1; i <= n; i++) dis[i] = g[1][i];
memset(visit, false, sizeof(visit));
visit[1] = true;
for(int k = 1; k < n; k++) {
min = 1e8;
for(int i = 1; i <= n; i++) {
if(!visit[i] && min>dis[i]) {
min = dis[i];
v = i;
}
}
visit[v] = true;
for(int i = 1; i <= n; i++) {
if(!visit[i] && dis[i]>g[v][i]) {
dis[i] = g[v][i];
}
}
tot += min;
}
return tot;
}
int main() {
freopen("data.in", "r", stdin);
scanf("%d", &Case);
while(Case--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lf%lf", &x[i], &y[i]);
for(int i = 1; i <= n; i++) {
g[i][i] = 0.0;
for(int j = i+1; j <= n; j++) {
g[i][j] = g[j][i] = Cal(i, j);
}
}
double ans = prim();
printf("%.2f\n", ans);
if(Case) printf("\n");
}
return 0;
}
stl优先队列的简单用法
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct comp {
bool operator () (int a, int b) {
return a > b;
}
};
int main() {
freopen("data.in", "r", stdin);
priority_queue <int, vector<int>, comp> q;
q.push(11); q.push(0); q.push(22); q.push(16); q.push(6); q.push(8); q.push(100);
while(!q.empty()) {
int x = q.top(); q.pop();
cout << x << endl;
}
return 0;
}
输出：
6
11
22
二分图最大匹配
int n, match[N];
bool visit[N], g[N][N];
bool find(int u) {
for(int i = 0; i < m; i++) {
if(g[u][i] && !visit[i]) {
visit[i] = true;
if(match[i]==-1 || find(match[i])) {
match[i] = u;
return true;
}
}
}
return false;
}
int maxMatch() {
int ans = 0;
memset(match, -1, sizeof(match));
for(int i = 0; i < n; i++) {
if(find(i)) ans++;
memset(visit, false, sizeof(visit));
}
return ans;
}
康托展开
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 10;
int p[N], fac[N];
int Cal(int p[], int n) {
int ans = 0;
for(int i = 0; i < n; i++) {
int ct = 0;
for(int j = i+1; j < n; j++) {
if(p[j] < p[i]) ct++;
}
ans += ct*fac[n-i-1];
}
return ans+1;
}
int main() {
int n;
fac[0] = 1;
for(int i = 1; i < N; i ++) fac[i] = fac[i-1]*i;
while(cin >> n) {
for(int i = 0; i < n; i++) cin >> p[i];
int ans = Cal(p, n);
cout << ans << endl;
}
return 0;
}
最小费用(最大)流
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
int sumFlow;
const int MAXN = 1010;
const int MAXM = 1000200;
const int INF = 1000000000;
struct Edge
{
int u, v, cap, cost;
int next;
}edge[MAXM<<2];
int NE;
int head[MAXN], dist[MAXN], pp[MAXN];
bool vis[MAXN];
void init()
{
NE = 0;
memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int cap, int cost)
{
edge[NE].u = u; edge[NE].v = v; edge[NE].cap = cap; edge[NE].cost = cost;
edge[NE].next = head[u]; head[u] = NE++;
edge[NE].u = v; edge[NE].v = u; edge[NE].cap = 0; edge[NE].cost = -cost;
edge[NE].next = head[v]; head[v] = NE++;
}
bool SPFA(int s, int t, int n)
{
int i, u, v;
queue <int> qu;
memset(vis,false,sizeof(vis));
memset(pp,-1,sizeof(pp));
for(i = 0; i <= n; i++) dist[i] = INF;
vis[s] = true; dist[s] = 0;
qu.push(s);
while(!qu.empty())
{
u = qu.front(); qu.pop(); vis[u] = false;
for(i = head[u]; i != -1; i = edge[i].next)
{
v = edge[i].v;
if(edge[i].cap && dist[v] > dist[u] + edge[i].cost)
{
dist[v] = dist[u] + edge[i].cost;
pp[v] = i;
if(!vis[v])
{
qu.push(v);
vis[v] = true;
}
}
}
}
if(dist[t] == INF) return false;
return true;
}
int MCMF(int s, int t, int n) // minCostMaxFlow
{
int flow = 0; // 总流量
int i, minflow, mincost;
mincost = 0;
while(SPFA(s, t, n))
{
minflow = INF + 1;
for(i = pp[t]; i != -1; i = pp[edge[i].u])
if(edge[i].cap < minflow)
minflow = edge[i].cap;
flow += minflow;
for(i = pp[t]; i != -1; i = pp[edge[i].u])
{
edge[i].cap -= minflow;
edge[i^1].cap += minflow;
}
mincost += dist[t] * minflow;
}
sumFlow = flow; // 最大流
return mincost;
}
日期类
int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
class Date {
public:
//判断是否闰年
inline static bool isLeap(int year) {
return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}
int year, month, day;
Date() {}
Date(int y, int m, int d) : year(y), month(m), day(d) {}
//判断日期是否合法
inline bool isLegal() const {
if (month <= 0 || month > 12) {
return false;
}
if (month == 2) {
return day > 0 && day <= 28 + isLeap(year);
}
return day > 0 && day <= days[month - 1];
}
//与另一个日期比较
inline int compareTo(const Date &other) const {
if (year != other.year) {
return year - other.year;
}
if (month != other.month) {
return month - other.month;
}
return day - other.day;
}
//返回当前日期是星期几 0 (Sunday) ... 6 (Saturday)
inline int toWeekday() const {
int tm = month >= 3 ? (month - 2) : (month + 10);
int ty = month >= 3 ? year : (year - 1);
return (ty + ty / 4 - ty / 100 + ty / 400 + (int)(2.6 * tm - 0.2) + day) % 7;
}
//将日期转换为偏移量
inline int toInt() const {
int ret = year * 365 + (year - 1) / 4 - (year - 1) / 100 + (year - 1) / 400;
days[1] += isLeap(year);
for (int i = 0; i < month - 1; ret += days[i++]);
days[1] = 28;
return ret + day;
}
//根据给定的偏移量设置当前日期
inline void fromInt(int a) {
year = a / 146097 * 400;
for (a %= 146097; a >= 365 + isLeap(year); a -= 365 + isLeap(year), year++);
days[1] += isLeap(year);
for (month = 1; a >= days[month - 1]; a -= days[month - 1], month++);
days[1] = 28;
day = a + 1;
}
};
不带size域的treap
// 不带size域的treap
class Treap {
public:
const static int MaxN = 100000;
int root, tsize, l[MaxN], r[MaxN], p[MaxN];
int key[MaxN];
void rot_l(int &x) { //before using this function, please ensure that the right son of x exist
int tmp = r[x];
r[x] = l[tmp]; l[tmp] = x;
x = tmp;
}
void rot_r(int &x) { //before using this function, please ensure that the left son of x exist
int tmp = l[x];
l[x] = r[tmp]; r[tmp] = x;
x = tmp;
}
Treap():root(-1),tsize(-1) {}
void insert(int &root, const int &x) {
if(root == -1) {
key[++tsize] = x;
root = tsize;
p[root] = rand();
l[root] = r[root] = -1;
}
else if(x <= key[root]) {
insert(l[root], x);
if(p[l[root]] > p[root]) rot_r(root);
}
else {
insert(r[root], x);
if(p[r[root]] > p[root]) rot_l(root);
}
}
void del(int &root, const int &x) {
if(key[root] == x) {
if(l[root]==-1 && r[root]==-1) root = -1;
else if(l[root] == -1) root = r[root];
else if(r[root] == -1) root = l[root];
else {
if(p[l[root]] > p[r[root]]) {
rot_r(root);
del(r[root], x);
}
else {
rot_l(root);
del(l[root], x);
}
}
}
else if(x < key[root]) del(l[root], x);
else del(r[root], x);
}
bool find(int &root, const int &x) {
if(root == -1) return false;
if(x == key[root]) return true;
else if(x < key[root]) return find(l[root], x);
else return find(r[root], x);
}
};
带size域的treap
//带size的treap
class Treap {
public:
const static int MaxN = 100000;
int root, tsize, l[MaxN], r[MaxN], p[MaxN], nsize[MaxN];
int key[MaxN];
void maintain(const int &root) {
int ta, tb;
ta = l[root]==-1? 0 : nsize[l[root]];
tb = r[root]==-1? 0 : nsize[r[root]];
nsize[root] = ta+tb+1;
}
void rot_l(int &x) { //before using this function, please ensure that the right son of x exist
int tmp = r[x];
r[x] = l[tmp]; maintain(x);
l[tmp] = x; x = tmp; maintain(x);
}
void rot_r(int &x) { //before using this function, please ensure that the left son of x exist
int tmp = l[x];
l[x] = r[tmp]; maintain(x);
r[tmp] = x; x = tmp; maintain(x);
}
Treap():root(-1),tsize(-1) {}
void insert(int &root, const int &x) {
if(root == -1) {
key[++tsize] = x;
root = tsize;
p[root] = rand();
l[root] = r[root] = -1;
nsize[root] = 1;
}
else if(x <= key[root]) {
insert(l[root], x);
if(p[l[root]] > p[root]) rot_r(root);
}
else {
insert(r[root], x);
if(p[r[root]] > p[root]) rot_l(root);
}
maintain(root);
}
void del(int &root, const int &x) {
if(key[root] == x) {
if(l[root]==-1 && r[root]==-1) root = -1;
else if(l[root] == -1) root = r[root];
else if(r[root] == -1) root = l[root];
else {
if(p[l[root]] > p[r[root]]) {
rot_r(root);
del(r[root], x);
}
else {
rot_l(root);
del(l[root], x);
}
}
}
else if(x < key[root]) del(l[root], x);
else del(r[root], x);
if(root != -1) maintain(root);
}
int kthElement(const int &root, int k) {
int ta;
ta = l[root]==-1? 0 : nsize[l[root]];
if(ta >= k) return kthElement(l[root], k);
else if(ta+1 == k) return key[root];
else return kthElement(r[root], k-ta-1);
}
bool find(int &root, const int &x) {
if(root == -1) return false;
if(x == key[root]) return true;
else if(x < key[root]) return find(l[root], x);
else return find(r[root], x);
}
};
Splay Top-down实现
class SplayTree
{
public:
SplayTree();
int getMaxValure();
int getMinValure();
void deleteElement(const int &x);
void insertElement(const int &x);
bool findElement(const int &x);
int preElement(const int &x);
int succElement(const int &x);
private:
struct node
{
int key;
node *lchild, *rchild;
node(){}
node(const int &x):key(x) {}
}*root, *nullnode;
void Zig(node *&x); //右旋
void Zag(node *&x); //左旋
void splay(node *&root, const int &x);
};
SplayTree::SplayTree()
{
nullnode = new node();
nullnode->lchild = nullnode;
nullnode->rchild = nullnode;
root = nullnode;
}
int SplayTree::getMaxValure()
{
node *p = root;
while(p->rchild != nullnode) p = p->rchild;
splay(root, p->key);
return p->key;
}
int SplayTree::getMinValure()
{
node *p = root;
while(p->lchild != nullnode) p = p->lchild;
splay(root, p->key);
return p->key;
}
void SplayTree::deleteElement(const int &x)
{
node *newnode;
splay(root, x);
if(root->key != x) return;
if(root->lchild == nullnode)
newnode = root->rchild;
else
{
newnode = root->lchild;
splay(newnode, x);
newnode->rchild = root->rchild;
}
delete root;
root = newnode;
}
void SplayTree::insertElement(const int &x)
{
node *newnode = new node(x);
if(root == nullnode)
{
root = newnode;
root->lchild = nullnode;
root->rchild = nullnode;
return;
}
splay(root, x);
if(x < root->key)
{
newnode->lchild = root->lchild;
root->lchild = nullnode;
newnode->rchild = root;
root = newnode;
}
else
{
newnode->rchild = root->rchild;
root->rchild = nullnode;
newnode->lchild = root;
root = newnode;
}
}
void SplayTree::Zig(node *&x)
{
node *y = x->lchild;
x->lchild = y->rchild;
y->rchild = x;
x = y;
}
void SplayTree::Zag(node *&x)
{
node *y = x->rchild;
x->rchild = y->lchild;
y->lchild = x;
x = y;
}
void SplayTree::splay(node *&root, const int &x)
{
node headnode;
node *ltree, *rtree;
headnode.lchild = headnode.rchild = nullnode;
ltree = rtree = &headnode;
while(root->key != x)
{
if(x < root->key)
{
if(root->lchild!=nullnode && x<root->lchild->key)
Zig(root);
if(root->lchild == nullnode) break;
rtree->lchild = root;
rtree = root;
root = root->lchild;
}
else
{
if(root->rchild!=nullnode && root->rchild->key<x)
Zag(root);
if(root->rchild == nullnode) break;
ltree->rchild = root;
ltree = root;
root = root->rchild;
}
}
ltree->rchild = root->lchild;
root->lchild = headnode.rchild;
rtree->lchild = root->rchild;
root->rchild = headnode.lchild;
}
bool SplayTree::findElement(const int &x)
{
splay(root, x);
if(root->key == x) return true;
else return false;
}
int SplayTree::preElement(const int &x)
{
int ans = 0;
splay(root, x);
node *p = root;
while(p != nullnode)
{
if(p->key < x)
{
ans = p->key;
p = p->rchild;
}
else p = p->lchild;
}
return ans;
}
int SplayTree::succElement(const int &x)
{
int ans = 0x1fffffff;
splay(root, x);
node *p = root;
while(p != nullnode)
{
if(p->key > x)
{
ans = p->key;
p = p->lchild;
}
else p = p->rchild;
}
return ans;
}
自适应辛普森公式
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long llg;
//本函数在模板中无意义，需根据不同的积分表达式编写
double F(double x) {
return x;
}
double simpson(double a, double b) {
double c = (a+b)/2;
return (F(a)+4*F(c)+F(b))*(b-a)/6;
}
double asr(double a, double b, double eps, double A) {
double c = (a+b)/2;
double L = simpson(a, c), R = simpson(c, b);
if(fabs(L+R-A) <= 15*eps) return L+R+(L+R-A)/15.0;
return asr(a, c, eps/2, L) + asr(c, b, eps/2, R);
}
double asr(double a, double b, double eps) {
return asr(a, b, eps, simpson(a, b));
}
int main() {
freopen("data.in", "r", stdin);
cout << asr(0, 1, 1e-5) << endl;
return 0;
}
素数测试和因子分解
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef longlong llg;
const int S =70;
llg tot, p[80];
llg mullg(llg a, llg b, llg n)
{
llg ans =0, tmp = a%n;
while(b)
{
if(b &1) ans += tmp;
if(ans >= n) ans -= n;
b >>=1;
tmp <<=1;
if(tmp >= n) tmp -= n;
}
return ans;
}
llg powMod(llg a, llg b, llg n)
{
llg ans =1, tmp = a % n;
while(b)
{
if(b &1) ans = mullg(ans, tmp, n);
b >>=1;
tmp = mullg(tmp, tmp, n);
}
return ans;
}
bool witness(llg a, llg n)
{
int i, t =0;
llg x, tx, nn = n-1;
while((nn&1) ==0)
{
nn >>=1;
t++;
}
x = powMod(a, nn, n);
for(i =1; i <= t; i++)
{
tx = mullg(x, x, n);
if(tx==1&& x!=1&& x!=n-1)
return true;
x = tx;
}
if(x !=1) return true;
return false;
}
bool millerRabin(llg n)
{
int i;
llg a;
if(n <2) return false;
if(n ==2) return true;
for(i =1; i <= S; i++)
{
a = (llg)rand()%(n-1) +1;
if(witness(a, n))
return false;
}
return true;
}
llg Abs(llg x)
{
if(x <0) x =-x;
return x;
}
llg gcd(llg a, llg b)
{
if(b ==0) return a;
else return gcd(b, a%b);
}
llg pollardRho(llg n, int c)
{
int i =0;
llg x, y, k, d;
y = x = rand()%(n-1) +1;
k =2;
while(1)
{
i++;
x = (mullg(x, x, n)+c) % n;
d = gcd(Abs(y-x), n);
if(d!=1&& d!=n) return d;
if(y == x) return n;
if(i == k)
{
y = x;
k <<=1;
}
}
}
void findFac(llg n)
{
if(millerRabin(n))
{
p[tot++] = n;
return;
}
else
{
//if(depth > 100) return;
llg p = n;
while(p==n && p) p = pollardRho(p, rand()%(n-1)+1);
findFac(p);
findFac(n/p);
}
}
}}}关键词： 后缀数组 AC自动机 AC+dp 分数规划 二分图最小权 二分图最大权 2-sat 最大流 最短路径（负环判定）
最小生成树(kruskal、并查集) 最小生成树prim stl优先队列的简单用法 二分图最大匹配 康托展开 最小费用(最大)流 日期
Treap Splay 辛普森 因子分解
后缀数组
const int N = 40005;
int sa[N], rk[N], height[N];
int wa[N], wb[N], wv[N], wts[N];
inline bool cmp(int *r, int a, int b, int len) {
return (r[a]==r[b]) && (r[a+len]==r[b+len]);
}
void sortSA(char *r, int *sa, int n, int m){
int i, j, p, *x = wa, *y = wb, *t;
for(i = 0; i < m; i++)
wts[i] = 0;
for(i = 0; i < n; i++)
wts[x[i]=r[i]]++;
for(i = 1; i < m; i++)
wts[i] += wts[i-1];
for(i = n-1; i >= 0; i--)
sa[--wts[x[i]]] = i;
for(j = p = 1; p < n; j <<= 1, m = p){
for(p=0, i=n-j; i < n; i++)
y[p++] = i;
for(i = 0; i < n; i++){
if(sa[i] >= j)
y[p++] = sa[i] - j;
}
for(i = 0; i < m; i++)
wts[i] = 0;
for(i = 0; i < n; i++)
wts[wv[i]=x[y[i]]]++;
for(i = 1; i < m; i++)
wts[i] += wts[i-1];
for(i = n-1; i >= 0; i--)
sa[--wts[wv[i]]] = y[i];
for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1; i < n; i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j) ? p-1:p++;
}
}
void calHeight(char *r, int *sa, int n){
int i, j, k = 0;
for(i = 1; i <= n; i++) rk[sa[i]] = i;
for(i = 0; i < n; i++){
for(k? k--:0, j=sa[rk[i]-1]; r[i+k]==r[j+k]; k++);
height[rk[i]] = k;
}
}
AC自动机
struct node {
int ct;
node *pre, *next[26];
void init() {
ct = 0;
pre = 0;
memset(next, 0, sizeof(next));
}
};
int cnt; //节点总数
node *root, trie[500010];
node *queue[500010];
void insertStr(node *root, char *str) {
int index, len = strlen(str);
for(int i = 0; i < len; i++) {
index = str[i]-'a';
if(root->next[index] == 0) {
root->next[index] = &trie[++cnt];
root->next[index]->init();
}
root = root->next[index];
}
root->ct++;
}
void buildAC() {
int head, tail;
node *u, tmp;
queue[0] = root;
root->pre = root;
head = tail = 0;
while(head <= tail) {
u = queue[head++];
for(int i = 0; i < 26; i++) {
if(u->next[i] == 0) {
if(u == root) u->next[i] = root;
else u->next[i] = u->pre->next[i];
}
else {
if(u == root) u->next[i]->pre = root;
else u->next[i]->pre = u->pre->next[i];
queue[++tail] = u->next[i];
}
}
}
}
分数规划
（1） 一般分数规划的解法
简单总结一下解分数规划的一般步骤吧：
1.对于最小化目标函数r = ax/bx，则构造函数g(r)=min{ax - r*bx}
对于最大化目标函数r = ax/bx，等价于最小化目标函数bx/ax，因此同上。
2.由各种大科学家大神们证明得结论T_T：
(1)g(r)是单调减函数(有些离散情况下也有可能是单调不增加函数)，即随r的增加而减小。
(2)若r是最优解，则g(r)==0。。
3.建立模型二分r求解。
二分图最小权匹配
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
using namespace std;
const int N =105;
const int M =10005;
const int inf =0x1fffffff;
int n, m, tot, lx[N], ly[N], match[N], h[N], v[M], w[M], nxt[M];
bool visx[N], visy[N];
int lack;
void add(int a, int b, int c)
{
v[tot] = b;
w[tot] = c;
nxt[tot] = h[a];
h[a] = tot++;
}
bool find(int u)
{
int i, t;
visx[u] =true;
for(i = h[u]; i !=-1; i = nxt[i])
if(!visy[v[i]])
{
t = w[i] - lx[u] - ly[v[i]];
if(t ==0)
{
visy[v[i]] =true;
if(match[v[i]]==-1|| find(match[v[i]]))
{
match[v[i]] = u;
return true;
}
}
else if(t >0)
lack = min(lack, t);
}
return false;
}
int calMatch(int n) {
int ans = 0;
for(int i =1; i <= n; i++)
{
lx[i] = inf;
ly[i] =0;
for(int j = h[i]; j !=-1; j = nxt[j])
lx[i] = min(lx[i], w[j]);
}
memset(match, -1, sizeof(match));
for(int i =1; i <= n; i++)
{
memset(visx, false, sizeof(visx));
memset(visy, false, sizeof(visy));
lack = inf;
while(!find(i))
{
for(int j =1; j <= n; j++)
{
if(visx[j]) lx[j] += lack;
if(visy[j]) ly[j] -= lack;
}
memset(visx, false, sizeof(visx));
memset(visy, false, sizeof(visy));
}
}
ans = 0;
for(int i =1; i <= n; i++) ans = ans + lx[i] + ly[i];
return ans;
}
二分图最大权匹配
#include <iostream>
#include <cstdio>
#include <cstring>
usingnamespace std;
constint N =310;
constint inf =0x1fffffff;
int n, lx[N], ly[N], match[N], w[N][N];
bool visx[N], visy[N];
int lack;
int getNum()
{
char c;
int ans =0;
c = getchar();
while(c<'0'|| c>'9') c = getchar();
while(c>='0'&& c<='9')
{
ans = ans*10+c-'0';
c = getchar();
}
return ans;
}
bool find(int u)
{
int i, t;
visx[u] =true;
for(i =1; i <= n; i++)
if(!visy[i])
{
t = lx[u] + ly[i] - w[u][i];
if(t ==0)
{
visy[i] =true;
if(match[i]==-1|| find(match[i]))
{
match[i] = u;
returntrue;
}
}
elseif(t >0)
lack = min(lack, t);
}
returnfalse;
}
int main()
{
int i, j, ans;
while(scanf("%d", &n) != EOF)
{
for(i =1; i <= n; i++)
{
lx[i] = ly[i] =0;
for(j =1; j <= n; j++)
{
w[i][j] = getNum();
lx[i] = max(lx[i], w[i][j]);
}
}
memset(match, -1, sizeof(match));
for(i =1; i <= n; i++)
{
memset(visx, false, sizeof(visx));
memset(visy, false, sizeof(visy));
lack = inf;
while(!find(i))
{
for(j =1; j <= n; j++)
{
if(visx[j]) lx[j] -= lack;
if(visy[j]) ly[j] += lack;
}
memset(visx, false, sizeof(visx));
memset(visy, false, sizeof(visy));
}
}
ans =0;
for(i =1; i <= n; i++) ans = ans + lx[i] + ly[i];
printf("%d\n", ans);
}
return0;
}
2-SAT问题（判定+求解）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1010;
int n; //原图中共有2*n个相对的节点。
int ct, depth, top, index[N<<1], d[N<<1], low[N<<1], stack[N<<1];
bool instack[N<<1], map[N<<1][N<<1], g[N<<1][N<<1];
int tot, et[N<<1], color[N<<1], op[N<<1];
bool visit[N<<1];
void initData() { //初始化数据，根据题意建图，建好的初始图为map
........
}
void dfs(int u) { //tarjan求强连通分量，缩点
int i, x;
d[u] = low[u] = depth++;
stack[++top] = u;
instack[u] =true;
for(i = 0; i < n+n; i++)
if(map[u][i]) {
if(d[i] == -1) {
dfs(i);
low[u] = min(low[u], low[i]);
}
else {
if(instack[i])
low[u] = min(low[u], d[i]);
}
}
if(low[u] == d[u]) {
ct++;
while(top)
{
x = stack[top--];
instack[x] = false;
index[x] = ct;
if(x == u) break;
}
}
}
void buildNewGraph() { //根据缩点建立新图
int i, j;
memset(g, false, sizeof(g));
for(i = 0; i < n+n; i++)
for(j = 0; j < n+n; j++)
if(map[i][j])
g[index[i]][index[j]] = true;
for(i = 1; i <= ct; i++)
for(j = i+1; j <= ct; j++)
swap(g[i][j], g[j][i]); //将新图中的边反向
for(i = 0; i < n; i++) { //根据原图的矛盾节点确定新图的矛盾节点
op[index[i]] = index[i+n];
op[index[i+n]] = index[i];
}
}
void transDfs(int u) {
int i;
visit[u] =true;
for(i = 1; i <= ct; i++)
if(!visit[i] && g[u][i])
transDfs(i);
et[++tot] = u;
}
void colorDfs(int u) {
int i;
color[u] = 0;
for(i = 1; i <= ct; i++)
if(color[i]==-1 && g[u][i])
colorDfs(i);
}
void generateAns() {
int i;
memset(visit, false, sizeof(visit));
tot = 0;
//拓扑排序
for(i = 1; i <= ct; i++)
if(!visit[i])
transDfs(i);
memset(color, -1, sizeof(color));
for(i = ct; i > 0; i--)
if(color[et[i]] == -1) {
color[et[i]] = 1;
//选择第一个未着色的顶点x, 把x染成红色1, 并把与之矛盾的节点y及其所有子孙节点染成蓝色0。
colorDfs(op[et[i]]);
}
}
void solve() {
int i;
depth = top = ct =0;
memset(d, -1, sizeof(d));
memset(instack, false, sizeof(instack));
for(i = 0; i < n+n; i++)
if(d[i] == -1)
dfs(i);
for(i = 0; i < n; i++)
if(index[i] == index[i+n])
break;
if(i < n) printf("NO\n");
else {
printf("YES\n");
buildNewGraph();
generateAns();
//printAns();
}
}
int main()
{
initData();
solve();
return 0;
}
最大流-dinic
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
const int Maxn = 20005;
const int Maxm = (200005<<1)+(Maxn<<1);
const int inf = 0x1fffffff;
int n, m, queue[Maxn], lab[Maxn];
int tot, h[Maxn], nxt[Maxm<<1], v[Maxm<<1], res[Maxm<<1];
void addEdge(int a, int b, int c) {
v[tot] = b; res[tot] = c; nxt[tot] = h[a]; h[a] = tot++;
v[tot] = a; res[tot] = 0; nxt[tot] = h[b]; h[b] = tot++;
}
bool bfs(int s, int t) {
int head, tail, u;
memset(lab, -1, sizeof(lab));
lab[s] = head = tail =0;
queue[0] = s;
while(head <= tail) {
u = queue[head++];
for(int i = h[u]; i != -1; i = nxt[i])
if(res[i]>0 && lab[v[i]]==-1) {
lab[v[i]] = lab[u] +1;
queue[++tail] = v[i];
}
}
if(lab[t] != -1) return true;
else return false;
}
int dinicDfs(int delta, int u, int t) {
int sum =0, tmp;
if(u == t) return delta;
else {
for(int i = h[u]; i != -1; i = nxt[i])
if(lab[v[i]]==lab[u]+1 && res[i]>0) {
tmp = dinicDfs(min(delta, res[i]), v[i], t);
sum += tmp;
delta -= tmp;
res[i] -= tmp;
res[i^1] += tmp;
if(delta == 0) break;
}
if(sum == 0) lab[u] = -1;
return sum;
}
}
int maxFlow(int s, int t) {
int ans =0;
while(bfs(s, t))
ans += dinicDfs(inf, s, t);
return ans;
}
int main()
{
int a, b, c, s, t;
freopen("data.txt", "r", stdin);
while(scanf("%d%d", &n, &m) != EOF) {
s = 0; t = n+1;
tot = 0;
for(int i = 0; i <= t; i++) h[i] = -1;
for(int i = 1; i <= n; i++) {
scanf("%d%d", &a, &b);
addEdge(s, i, a); addEdge(i, t, b);
}
while(m--) {
scanf("%d%d%d", &a, &b, &c);
addEdge(a, b, c); addEdge(b, a, c);
}
int ans = maxFlow(s, t);
cout << ans << endl;
}
return 0;
}
最短路径（spfa判负环）
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 550;
const int M = 3000<<1;
int Case, n, m, w;
int tot, h[N], nxt[M], c[M], v[M];
int used[N], dis[N];
bool visit[N];
void add(int s, int t, int e) {
v[tot] = t; c[tot] = e;
nxt[tot] = h[s]; h[s] = tot++;
}
bool spfa(int s) {
int u;
queue <int> q; while(!q.empty()) q.pop();
memset(visit, false, sizeof(visit));
memset(used, 0, sizeof(used));
for(int i = 1; i <= n; i++) dis[i] = 0x1fffffff; dis[0] = 0;
used[0] = 1;
q.push(s);
while(!q.empty()) {
u = q.front(); q.pop();
visit[u] = false;
for(int p = h[u]; p != -1; p = nxt[p]) {
if(dis[v[p]] > dis[u] + c[p]) {
dis[v[p]] = dis[u] + c[p];
if(!visit[v[p]]) {
visit[v[p]] = true;
q.push(v[p]);
used[v[p]]++;
if(used[v[p]] >= n) return true;
}
}
}
}
return false;
}
int main() {
int s, t, e;
scanf("%d", &Case);
while(Case--) {
scanf("%d%d%d", &n, &m, &w);
memset(h, -1, sizeof(h)); tot = 0;
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &s, &t, &e);
add(s, t, e);
add(t, s, e);
}
for(int i = 0; i < w; i++) {
scanf("%d%d%d", &s, &t, &e);
add(s, t, -e);
}
for(int i = 1; i <= n; i++) add(0, i, 0);
if(spfa(0)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
最小生成树 (kruskal、并查集)
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 200010;
struct node {
int x, y, cost;
}e[N];
int n, m, father[N];
bool cmp(const node &a, const node &b) {
return a.cost < b.cost;
}
int getFather(int u) {
if(father[u] != u) father[u] = getFather(father[u]);
return father[u];
}
int kruskal() {
int fa, fb, sum = 0;
for(int i = 0; i < n; i++) father[i] = i;
sort(e, e+m, cmp);
for(int i = 0; i < m; i++) {
fa = getFather(e[i].x); fb = getFather(e[i].y);
if(fa == fb) continue;
else {
father[fb] = father[fa];
sum += e[i].cost;
}
}
return sum;
}
int main() {
int tot;
freopen("data.in", "r", stdin);
while(scanf("%d%d", &n, &m) != EOF) {
if(n==0 && m==0) break;
tot = 0;
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].cost);
tot += e[i].cost;
}
int ans = tot-kruskal();
printf("%d\n", ans);
}
return 0;
}
最小生成树prim
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 105;
int Case, n;
bool visit[N];
double x[N], y[N], dis[N], g[N][N];
double Cal(int a, int b) {
double tx=x[a]-x[b], ty=y[a]-y[b];
return sqrt(tx*tx + ty*ty);
}
double prim() {
double tot = 0.0, min;
int v;
for(int i = 1; i <= n; i++) dis[i] = g[1][i];
memset(visit, false, sizeof(visit));
visit[1] = true;
for(int k = 1; k < n; k++) {
min = 1e8;
for(int i = 1; i <= n; i++) {
if(!visit[i] && min>dis[i]) {
min = dis[i];
v = i;
}
}
visit[v] = true;
for(int i = 1; i <= n; i++) {
if(!visit[i] && dis[i]>g[v][i]) {
dis[i] = g[v][i];
}
}
tot += min;
}
return tot;
}
int main() {
freopen("data.in", "r", stdin);
scanf("%d", &Case);
while(Case--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lf%lf", &x[i], &y[i]);
for(int i = 1; i <= n; i++) {
g[i][i] = 0.0;
for(int j = i+1; j <= n; j++) {
g[i][j] = g[j][i] = Cal(i, j);
}
}
double ans = prim();
printf("%.2f\n", ans);
if(Case) printf("\n");
}
return 0;
}
stl优先队列的简单用法
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct comp {
bool operator () (int a, int b) {
return a > b;
}
};
int main() {
freopen("data.in", "r", stdin);
priority_queue <int, vector<int>, comp> q;
q.push(11); q.push(0); q.push(22); q.push(16); q.push(6); q.push(8); q.push(100);
while(!q.empty()) {
int x = q.top(); q.pop();
cout << x << endl;
}
return 0;
}
输出：
6
11
22
二分图最大匹配
int n, match[N];
bool visit[N], g[N][N];
bool find(int u) {
for(int i = 0; i < m; i++) {
if(g[u][i] && !visit[i]) {
visit[i] = true;
if(match[i]==-1 || find(match[i])) {
match[i] = u;
return true;
}
}
}
return false;
}
int maxMatch() {
int ans = 0;
memset(match, -1, sizeof(match));
for(int i = 0; i < n; i++) {
if(find(i)) ans++;
memset(visit, false, sizeof(visit));
}
return ans;
}
康托展开
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 10;
int p[N], fac[N];
int Cal(int p[], int n) {
int ans = 0;
for(int i = 0; i < n; i++) {
int ct = 0;
for(int j = i+1; j < n; j++) {
if(p[j] < p[i]) ct++;
}
ans += ct*fac[n-i-1];
}
return ans+1;
}
int main() {
int n;
fac[0] = 1;
for(int i = 1; i < N; i ++) fac[i] = fac[i-1]*i;
while(cin >> n) {
for(int i = 0; i < n; i++) cin >> p[i];
int ans = Cal(p, n);
cout << ans << endl;
}
return 0;
}
最小费用(最大)流
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
int sumFlow;
const int MAXN = 1010;
const int MAXM = 1000200;
const int INF = 1000000000;
struct Edge
{
int u, v, cap, cost;
int next;
}edge[MAXM<<2];
int NE;
int head[MAXN], dist[MAXN], pp[MAXN];
bool vis[MAXN];
void init()
{
NE = 0;
memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int cap, int cost)
{
edge[NE].u = u; edge[NE].v = v; edge[NE].cap = cap; edge[NE].cost = cost;
edge[NE].next = head[u]; head[u] = NE++;
edge[NE].u = v; edge[NE].v = u; edge[NE].cap = 0; edge[NE].cost = -cost;
edge[NE].next = head[v]; head[v] = NE++;
}
bool SPFA(int s, int t, int n)
{
int i, u, v;
queue <int> qu;
memset(vis,false,sizeof(vis));
memset(pp,-1,sizeof(pp));
for(i = 0; i <= n; i++) dist[i] = INF;
vis[s] = true; dist[s] = 0;
qu.push(s);
while(!qu.empty())
{
u = qu.front(); qu.pop(); vis[u] = false;
for(i = head[u]; i != -1; i = edge[i].next)
{
v = edge[i].v;
if(edge[i].cap && dist[v] > dist[u] + edge[i].cost)
{
dist[v] = dist[u] + edge[i].cost;
pp[v] = i;
if(!vis[v])
{
qu.push(v);
vis[v] = true;
}
}
}
}
if(dist[t] == INF) return false;
return true;
}
int MCMF(int s, int t, int n) // minCostMaxFlow
{
int flow = 0; // 总流量
int i, minflow, mincost;
mincost = 0;
while(SPFA(s, t, n))
{
minflow = INF + 1;
for(i = pp[t]; i != -1; i = pp[edge[i].u])
if(edge[i].cap < minflow)
minflow = edge[i].cap;
flow += minflow;
for(i = pp[t]; i != -1; i = pp[edge[i].u])
{
edge[i].cap -= minflow;
edge[i^1].cap += minflow;
}
mincost += dist[t] * minflow;
}
sumFlow = flow; // 最大流
return mincost;
}
日期类
int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
class Date {
public:
//判断是否闰年
inline static bool isLeap(int year) {
return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}
int year, month, day;
Date() {}
Date(int y, int m, int d) : year(y), month(m), day(d) {}
//判断日期是否合法
inline bool isLegal() const {
if (month <= 0 || month > 12) {
return false;
}
if (month == 2) {
return day > 0 && day <= 28 + isLeap(year);
}
return day > 0 && day <= days[month - 1];
}
//与另一个日期比较
inline int compareTo(const Date &other) const {
if (year != other.year) {
return year - other.year;
}
if (month != other.month) {
return month - other.month;
}
return day - other.day;
}
//返回当前日期是星期几 0 (Sunday) ... 6 (Saturday)
inline int toWeekday() const {
int tm = month >= 3 ? (month - 2) : (month + 10);
int ty = month >= 3 ? year : (year - 1);
return (ty + ty / 4 - ty / 100 + ty / 400 + (int)(2.6 * tm - 0.2) + day) % 7;
}
//将日期转换为偏移量
inline int toInt() const {
int ret = year * 365 + (year - 1) / 4 - (year - 1) / 100 + (year - 1) / 400;
days[1] += isLeap(year);
for (int i = 0; i < month - 1; ret += days[i++]);
days[1] = 28;
return ret + day;
}
//根据给定的偏移量设置当前日期
inline void fromInt(int a) {
year = a / 146097 * 400;
for (a %= 146097; a >= 365 + isLeap(year); a -= 365 + isLeap(year), year++);
days[1] += isLeap(year);
for (month = 1; a >= days[month - 1]; a -= days[month - 1], month++);
days[1] = 28;
day = a + 1;
}
};
不带size域的treap
// 不带size域的treap
class Treap {
public:
const static int MaxN = 100000;
int root, tsize, l[MaxN], r[MaxN], p[MaxN];
int key[MaxN];
void rot_l(int &x) { //before using this function, please ensure that the right son of x exist
int tmp = r[x];
r[x] = l[tmp]; l[tmp] = x;
x = tmp;
}
void rot_r(int &x) { //before using this function, please ensure that the left son of x exist
int tmp = l[x];
l[x] = r[tmp]; r[tmp] = x;
x = tmp;
}
Treap():root(-1),tsize(-1) {}
void insert(int &root, const int &x) {
if(root == -1) {
key[++tsize] = x;
root = tsize;
p[root] = rand();
l[root] = r[root] = -1;
}
else if(x <= key[root]) {
insert(l[root], x);
if(p[l[root]] > p[root]) rot_r(root);
}
else {
insert(r[root], x);
if(p[r[root]] > p[root]) rot_l(root);
}
}
void del(int &root, const int &x) {
if(key[root] == x) {
if(l[root]==-1 && r[root]==-1) root = -1;
else if(l[root] == -1) root = r[root];
else if(r[root] == -1) root = l[root];
else {
if(p[l[root]] > p[r[root]]) {
rot_r(root);
del(r[root], x);
}
else {
rot_l(root);
del(l[root], x);
}
}
}
else if(x < key[root]) del(l[root], x);
else del(r[root], x);
}
bool find(int &root, const int &x) {
if(root == -1) return false;
if(x == key[root]) return true;
else if(x < key[root]) return find(l[root], x);
else return find(r[root], x);
}
};
带size域的treap
//带size的treap
class Treap {
public:
const static int MaxN = 100000;
int root, tsize, l[MaxN], r[MaxN], p[MaxN], nsize[MaxN];
int key[MaxN];
void maintain(const int &root) {
int ta, tb;
ta = l[root]==-1? 0 : nsize[l[root]];
tb = r[root]==-1? 0 : nsize[r[root]];
nsize[root] = ta+tb+1;
}
void rot_l(int &x) { //before using this function, please ensure that the right son of x exist
int tmp = r[x];
r[x] = l[tmp]; maintain(x);
l[tmp] = x; x = tmp; maintain(x);
}
void rot_r(int &x) { //before using this function, please ensure that the left son of x exist
int tmp = l[x];
l[x] = r[tmp]; maintain(x);
r[tmp] = x; x = tmp; maintain(x);
}
Treap():root(-1),tsize(-1) {}
void insert(int &root, const int &x) {
if(root == -1) {
key[++tsize] = x;
root = tsize;
p[root] = rand();
l[root] = r[root] = -1;
nsize[root] = 1;
}
else if(x <= key[root]) {
insert(l[root], x);
if(p[l[root]] > p[root]) rot_r(root);
}
else {
insert(r[root], x);
if(p[r[root]] > p[root]) rot_l(root);
}
maintain(root);
}
void del(int &root, const int &x) {
if(key[root] == x) {
if(l[root]==-1 && r[root]==-1) root = -1;
else if(l[root] == -1) root = r[root];
else if(r[root] == -1) root = l[root];
else {
if(p[l[root]] > p[r[root]]) {
rot_r(root);
del(r[root], x);
}
else {
rot_l(root);
del(l[root], x);
}
}
}
else if(x < key[root]) del(l[root], x);
else del(r[root], x);
if(root != -1) maintain(root);
}
int kthElement(const int &root, int k) {
int ta;
ta = l[root]==-1? 0 : nsize[l[root]];
if(ta >= k) return kthElement(l[root], k);
else if(ta+1 == k) return key[root];
else return kthElement(r[root], k-ta-1);
}
bool find(int &root, const int &x) {
if(root == -1) return false;
if(x == key[root]) return true;
else if(x < key[root]) return find(l[root], x);
else return find(r[root], x);
}
};
Splay Top-down实现
class SplayTree
{
public:
SplayTree();
int getMaxValure();
int getMinValure();
void deleteElement(const int &x);
void insertElement(const int &x);
bool findElement(const int &x);
int preElement(const int &x);
int succElement(const int &x);
private:
struct node
{
int key;
node *lchild, *rchild;
node(){}
node(const int &x):key(x) {}
}*root, *nullnode;
void Zig(node *&x); //右旋
void Zag(node *&x); //左旋
void splay(node *&root, const int &x);
};
SplayTree::SplayTree()
{
nullnode = new node();
nullnode->lchild = nullnode;
nullnode->rchild = nullnode;
root = nullnode;
}
int SplayTree::getMaxValure()
{
node *p = root;
while(p->rchild != nullnode) p = p->rchild;
splay(root, p->key);
return p->key;
}
int SplayTree::getMinValure()
{
node *p = root;
while(p->lchild != nullnode) p = p->lchild;
splay(root, p->key);
return p->key;
}
void SplayTree::deleteElement(const int &x)
{
node *newnode;
splay(root, x);
if(root->key != x) return;
if(root->lchild == nullnode)
newnode = root->rchild;
else
{
newnode = root->lchild;
splay(newnode, x);
newnode->rchild = root->rchild;
}
delete root;
root = newnode;
}
void SplayTree::insertElement(const int &x)
{
node *newnode = new node(x);
if(root == nullnode)
{
root = newnode;
root->lchild = nullnode;
root->rchild = nullnode;
return;
}
splay(root, x);
if(x < root->key)
{
newnode->lchild = root->lchild;
root->lchild = nullnode;
newnode->rchild = root;
root = newnode;
}
else
{
newnode->rchild = root->rchild;
root->rchild = nullnode;
newnode->lchild = root;
root = newnode;
}
}
void SplayTree::Zig(node *&x)
{
node *y = x->lchild;
x->lchild = y->rchild;
y->rchild = x;
x = y;
}
void SplayTree::Zag(node *&x)
{
node *y = x->rchild;
x->rchild = y->lchild;
y->lchild = x;
x = y;
}
void SplayTree::splay(node *&root, const int &x)
{
node headnode;
node *ltree, *rtree;
headnode.lchild = headnode.rchild = nullnode;
ltree = rtree = &headnode;
while(root->key != x)
{
if(x < root->key)
{
if(root->lchild!=nullnode && x<root->lchild->key)
Zig(root);
if(root->lchild == nullnode) break;
rtree->lchild = root;
rtree = root;
root = root->lchild;
}
else
{
if(root->rchild!=nullnode && root->rchild->key<x)
Zag(root);
if(root->rchild == nullnode) break;
ltree->rchild = root;
ltree = root;
root = root->rchild;
}
}
ltree->rchild = root->lchild;
root->lchild = headnode.rchild;
rtree->lchild = root->rchild;
root->rchild = headnode.lchild;
}
bool SplayTree::findElement(const int &x)
{
splay(root, x);
if(root->key == x) return true;
else return false;
}
int SplayTree::preElement(const int &x)
{
int ans = 0;
splay(root, x);
node *p = root;
while(p != nullnode)
{
if(p->key < x)
{
ans = p->key;
p = p->rchild;
}
else p = p->lchild;
}
return ans;
}
int SplayTree::succElement(const int &x)
{
int ans = 0x1fffffff;
splay(root, x);
node *p = root;
while(p != nullnode)
{
if(p->key > x)
{
ans = p->key;
p = p->lchild;
}
else p = p->rchild;
}
return ans;
}
自适应辛普森公式
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long llg;
//本函数在模板中无意义，需根据不同的积分表达式编写
double F(double x) {
return x;
}
double simpson(double a, double b) {
double c = (a+b)/2;
return (F(a)+4*F(c)+F(b))*(b-a)/6;
}
double asr(double a, double b, double eps, double A) {
double c = (a+b)/2;
double L = simpson(a, c), R = simpson(c, b);
if(fabs(L+R-A) <= 15*eps) return L+R+(L+R-A)/15.0;
return asr(a, c, eps/2, L) + asr(c, b, eps/2, R);
}
double asr(double a, double b, double eps) {
return asr(a, b, eps, simpson(a, b));
}
int main() {
freopen("data.in", "r", stdin);
cout << asr(0, 1, 1e-5) << endl;
return 0;
}
素数测试和因子分解
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef longlong llg;
const int S =70;
llg tot, p[80];
llg mullg(llg a, llg b, llg n)
{
llg ans =0, tmp = a%n;
while(b)
{
if(b &1) ans += tmp;
if(ans >= n) ans -= n;
b >>=1;
tmp <<=1;
if(tmp >= n) tmp -= n;
}
return ans;
}
llg powMod(llg a, llg b, llg n)
{
llg ans =1, tmp = a % n;
while(b)
{
if(b &1) ans = mullg(ans, tmp, n);
b >>=1;
tmp = mullg(tmp, tmp, n);
}
return ans;
}
bool witness(llg a, llg n)
{
int i, t =0;
llg x, tx, nn = n-1;
while((nn&1) ==0)
{
nn >>=1;
t++;
}
x = powMod(a, nn, n);
for(i =1; i <= t; i++)
{
tx = mullg(x, x, n);
if(tx==1&& x!=1&& x!=n-1)
return true;
x = tx;
}
if(x !=1) return true;
return false;
}
bool millerRabin(llg n)
{
int i;
llg a;
if(n <2) return false;
if(n ==2) return true;
for(i =1; i <= S; i++)
{
a = (llg)rand()%(n-1) +1;
if(witness(a, n))
return false;
}
return true;
}
llg Abs(llg x)
{
if(x <0) x =-x;
return x;
}
llg gcd(llg a, llg b)
{
if(b ==0) return a;
else return gcd(b, a%b);
}
llg pollardRho(llg n, int c)
{
int i =0;
llg x, y, k, d;
y = x = rand()%(n-1) +1;
k =2;
while(1)
{
i++;
x = (mullg(x, x, n)+c) % n;
d = gcd(Abs(y-x), n);
if(d!=1&& d!=n) return d;
if(y == x) return n;
if(i == k)
{
y = x;
k <<=1;
}
}
}
void findFac(llg n)
{
if(millerRabin(n))
{
p[tot++] = n;
return;
}
else
{
//if(depth > 100) return;
llg p = n;
while(p==n && p) p = pollardRho(p, rand()%(n-1)+1);
findFac(p);
findFac(n/p);
}
}