天津大学 ACM模板.pdf-资料库

你若是天才，我便做疯子！ ACM 笔记 TJU ACM tmeteorj

版本 V1.0 V2.0 时间 2012.12.04 2013.11.08 修订人 tmeteorj tmeteorj

图图图论论论 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 111 定理 ..................................................................1 割点割边 .........................................................1 树的分治 .........................................................1 无向图的最大匹配........................................2 无向图的最大环 ............................................2 Dinic 最大流 O（V^2*E） ..........................2 Sap 最大流 O（V*E*logF ...........................3 ZKW_Cost _Flow ..............................................3 平面图网络流.................................................4 混合图的欧拉回路........................................5 最大权闭合图.................................................6 最大密度子图.................................................6 最小边割集 .....................................................7 二分图最小权覆盖集 ...................................8 最优比例生成树 ............................................8 曼哈顿距离生成树........................................9 最小限度生成树 ......................................... 10 次小生成树 .................................................. 11 树链剖分 ...................................................... 11 生成树计数 .................................................. 12 树中删除最少边形成n 连通集 .............. 13 N 阶完全图生成子图数量........................ 14 计计计算算算几几几何何何 ... ... ... ... ... ... ... ... ... ... 111 444 公式 ............................................................... 14 二维计算几何库 ......................................... 15 //直线一般式转两点式 ............................ 15 //直线两点式转一般式 ............................ 15 //点 p 绕 o 逆时针旋转 alpha .............. 15 //向量 u 的倾斜角 ................................... 15 //oe 与 os 的夹角，夹角正负满足叉积15 //p 在 l 上的投影与 l 关系.................... 15 //p 在 l 上的垂足 .................................... 15 //求点 p 到线段 l 的最短距离,并返回线段上距该点最近的点 np ........................... 15 //求点 p 到直线 l 的最短距离 ............... 16 //线段之间最短距离 ................................ 16 //求矢量线段夹角的余弦 ........................ 16 //求矢量的夹角的余弦 ............................ 16 //求线段夹角 ............................................ 16 //求直线斜率 ............................................ 16 //直线倾斜角[0,Pi] ............................. 16 //点关于直线的对称点 ............................ 16 //判多边形是否逆时针 ............................ 16 //改变多边形时针顺序 ............................ 16 //判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线 .............................. 16 //判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线 .......................... 16 //判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出............................. 16 //判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回 0 ............... 16 //判点在线段上 ........................................ 16 //判点在线段端点左方 ............................ 16 //判线段相交 <=:不规范相交............... 16 //判点在多边形内部 ................................ 16 //多边形内部最长线段 ............................ 17 //凸包对踵点长度 .................................... 17 //判 p1,p2 是否在 l1,l2 两侧 ............ 17 //判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回 1 ........... 17 //求直线交点，必须存在交点，或者预判断【解析几何方法】................................. 17 //求线段交点，必须存在交点，或者预判断【平面几何方法】................................. 17 //三角形重心 ............................................ 17 //多边形重心 ............................................ 17 //求多边形面积 ........................................ 17 //解方程 ax^2+bx+c=0 ........................ 17 //线段与圆交点 ........................................ 18 //给出在任意多边形内部的一个点 ........ 18 //求在多边形外面的点到凸包的切点 .... 18 //判断点 p 在圆 c 内 ............................... 18 //求矩形第 4 个点 ................................... 18 //判两圆关系 ............................................ 18 //判圆与矩形关系,矩形水平 ................. 18 //射线关于平面的反射 ............................ 18 //两圆交点（预判断不相交情况） ........ 18 //圆外一点引圆的切线 ............................ 19 //圆 c1 上，与 c2 的外切点 .................. 19 //圆 c1 上，与 c2 的内切点 .................. 19 三维计算几何库 ......................................... 19 //平面法向量 ............................................ 19 //判定点是否在线段上，包括端点和共线 ..................................................................... 19 //判断点在平面上 .................................... 19 //判定点是否在空间三角形上，包括边界，三点共线无意义......................................... 19 //判定点是否在空间三角形上，不包括边界，三点共线无意义................................. 19 //判定两点在线段同侧，点在线段上返回 0，不共面无意义 ...................................... 19 //判定两点在线段异侧，点在平面上返回 0 .................................................................. 19 //判定两点在平面同侧，点在平面上返回 0 .................................................................. 20 //判定两点在平面异侧，点在平面上返回 0 .................................................................. 20 //判断直线平行 ........................................ 20 //判定两线段相交，不包括端点和部分重合................................................................. 20 //判定线段与空间三角形相交，包括交于边界和（部分）包含................................. 20 //判定线段与空间三角形相交，不包括交于边界和（部分）包含............................. 20 //面面平行 ................................................ 20 //判断直线垂直 ........................................ 20 //面面垂直 ................................................ 20 //判断两直线的位置关系 ........................ 20 //直线与平面关系 .................................... 20 //线面求交 ................................................ 20 //线线求交 ................................................ 20 //面面求交 ................................................ 20

//点线距离 ................................................ 20 //点面距离 ................................................ 20 //线线距离 ................................................ 20 //点线垂足 ................................................ 20 //已知四面体六边求体积 ........................ 20 //四面体体积 ............................................ 20 三角形 ........................................................... 20 凸包 ............................................................... 21 两凸包的最短距离..................................... 21 凸包的直径 .................................................. 22 凸包的最大内切圆..................................... 22 三维凸包 ...................................................... 22 半平面交 ...................................................... 23 平面最远点对.............................................. 24 网格 ............................................................... 24 两圆交面积 .................................................. 24 最小圆覆盖 .................................................. 24 单位圆覆盖最多点..................................... 25 最小球覆盖 .................................................. 25 圆和多边形的交 ......................................... 26 直线关于圆的反射..................................... 26 扇形的重心 .................................................. 28 三角形内部点数 ......................................... 28 Pick 公式求面积 ......................................... 28 共线最多的点的个数 ................................ 29 N 个点最多组成正方形个数 ................... 29 N 个点最多确定互不平行的直线 .......... 30 求多边形的核.............................................. 30 数数数学学学 ... ... ... ... ... ... ... ... ... ... ... ... ... ... 333 000 数论 ............................................................... 30 定理与定义 .................................................. 31 公式与序列 .................................................. 32 排列与组合 .................................................. 32 数学常用库 .................................................. 33 //筛素数 .................................................... 33 //筛欧拉函数 ............................................ 33 //筛约数个数、最小素数次数 ................ 33 //筛莫比乌斯函数 .................................... 33 //欧几里得 ................................................ 34 //扩展欧几里得 ........................................ 34 //乘法逆元，【确保有逆元】 ................ 34 //最小公倍数 ............................................ 34 //数位统计,[1,con]区间内数字出现次数................................................................. 34 //防高精度乘法 ........................................ 34 //快速幂取模 ............................................ 34 //米勒拉宾伪素数测试 ............................ 34 整数拆分 ...................................................... 34 连分数 ........................................................... 34 伯努利数 ...................................................... 34 伯努利公式求幂方和 ................................ 35 差分序列 ...................................................... 35 差分序列求幂方和..................................... 36 定积分（龙贝格）..................................... 36 定积分（自适应辛普森） ....................... 36 线性规划（单纯型） ................................ 36 多项式乘法（FFT）................................... 37 莫比乌斯反演(定义) ................................ 38 莫比乌斯反演(例程) ................................ 38 表达式求值 .................................................. 39 模线性方程组.............................................. 39 Lucas-组合数取模....................................... 39 快速组合数取模 ......................................... 40 整数的质因数分解..................................... 40 递归求等比数列之和 ................................ 40 最优子区间 .................................................. 40 高精度 ........................................................... 41 第K 个与m 互质的数............................... 42 行列式计算 .................................................. 42 排列P（n，m）最后非零位 .................. 42 取石子游戏 .................................................. 42 Nim 游戏必胜方法数 ................................ 43 猜数游戏 ...................................................... 43 逆序数为m 的最小序列 .......................... 43 区间最大权选取 ......................................... 43 第n 个回文数 ............................................. 43 权值最大子矩形 ......................................... 44 ............................................... 44 ....................................................... 44 .......................................... 44 ..................................... 45 带限制的项链计数整数拆分的最大的最小公倍数 .............. 45 ............................ 46 第二类斯特林数奇偶性数数数据据据结结结构构构 ... ... ... ... ... ... ... ... ... ... ... 444 666 堆 .................................................................... 46 AC 自动机 ..................................................... 46 划分树 ........................................................... 47 树状数组（第k 大值）............................ 47 树状数组（区域维护）............................ 47 树状数组（约瑟夫环）............................ 48 笛卡尔树（Treap） ................................... 48 笛卡尔树_2（Treap）............................... 49 二叉平衡树（AVL） .................................. 49 KD 树（空间距离前k 近点） ................. 50 Splay(动态数组).......................................... 51 Dancing links(精确覆盖) ........................... 52 块状链表 ...................................................... 53 KMP................................................................ 54 其其其它它它... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 555 444 C++库（不常用）....................................... 54 操作 ............................................................... 54 关于G++与C++的输入输出 .................... 55 nini1),gcd(niik1%)(modcbax

JAVA 汇总 ..................................................... 55 DP 优化 ......................................................... 56 前缀等于后缀的子串个数 ....................... 56 最长回文子串.............................................. 56 背包问题 ...................................................... 57 基数排序 ...................................................... 57 字符环的最小表示法 ................................ 57 最小循环矩阵.............................................. 57 最短非子序列长度..................................... 57 最长下降子序列长度与个数................... 58 最少偏序集个数 ......................................... 58 N 皇后问题构造方法................................. 58 N*M 数码有解判定 ................................... 59 堆排序最坏情况构造 ................................ 59

/ * * * * * * * * * * * * * * * * / 图论 / * * * * * * * * * * * * * * * * / /************************************/ 定理 /************************************/ 二部图中: 1、Konig 定理:最大匹配数等于最小覆盖数(顶点属于最小覆盖集,或与最小覆盖集中的某个顶点直接相连) 2、最大独立集等于最小边覆盖数(最小路径覆盖,注意路径是否可重，可重则还要求传递闭包)等于图的点数减去最大匹配数（点数相等时） 3、顶点的最大度数等于最小边染色数: 简证,二部图中没有奇环,对于欧环,可以用两种颜色不断重复来染色,所以只要保证最大度数顶点连接的边染不同色即可. 4.最大团等于补图的最大独立集。(建边时注意将集合分为二分图) 最大流最小割定理 1、网络流图中的最大流等于最小割. 平面图性质 1.欧拉公式）如果一个连通的平面图有 n 个点，m 条边和 f 个面，那么 f=m-n+2 2.每个平面图 G 都有一个与其对偶的平面图 G* G*中的每个点对应 G 中的一个面对于 G 中的每条边 e e 属于两个面 f1、f2，加入边(f1*， f2*) e 只属于一个面 f，加入回边(f*， f*) a.G 的面数等于 G*的点数，G*的点数等于 G 的面数，G 与 G*边数相同 b.G*中的环对应 G 中的割一一对应利用最短路求最小割对于一个 s-t 平面图，我们对其进行如下改造： 1.连接 s 和 t，得到一个附加面 2.求该图的对偶图 G*，令附加面对应的点为 s*，无界面对应的点为 t* 3.删去 s*和 t*之间的边一条从 s*到 t*的路径，就对应了一个 s-t 割！更进一步，如果我们令每条边的长度等于它的容量，那么最小割的容量就等于最短路的长度！最少添加边问题 1．最少添加有向边使的原图为强连通图的数量等于原图缩点后出度为 0 的点数和入度为 0 的点数的个数的最大值 2.添加最少边使原图成为双连通图的数量等于原图缩点后度数为 1 的点加 1 除以 2.(无向图也要缩点) /************************************/ 割点割边 /************************************/ /** init: memset(vis,false,sizeof(vis)); memset(cut,false,sizeof(cut)); memset(bridge,false,sizeof(bridge)); dfs(root,root,0); **/ bool vis[N]; int dep[N],low[N]; void dfs(int now,int fa,int deep){ vis[now]=true; dep[now]=low[now]=deep; int tot=0; for(int i=head[now];i!=-1;i=edge[i].nxt){ int to=edge[i].to; if(to==fa)continue; if(vis[to])low[now]=min(low[now],dep[to]); else{ dfs(to,now,deep+1); tot++; low[now]=min(low[now],low[to]); if((now==root&&tot>1)||(now!=root&&low[to]>=de p[now]))cut[now]=true; if(low[to]>dep[now])bridge[i]=bridge[i^1]=true ; } 1 } } /************************************/ 树的分治 /************************************/ /** 问：求树中所有路径长度小于 len 的点对个数 init: mark <-- false dfs(root) **/ bool mark[N]; int temp[N],cnt,size[N]; int n,len; void getsize(int x,int fa) { //以 x 为根的子树的结点数目 size[x]=1; for(int i=head[x]; i!=-1; i=edge[i].next) { int t=edge[i].to; if(mark[t]||t==fa) continue; getsize(t,x); size[x]+=size[t]; } } int bestroot(int x) { //找树的重心 getsize(x,x); int half=size[x]>>1; while(1) { int id=x,mmax=0; for(int i=head[x]; i!=-1; i=edge[i].next) { int t=edge[i].to; if(!mark[t]&&mmaxlen)return; temp[cnt++]=d; for(int t,i=head[now]; i!=-1; i=edge[i].next) { t=edge[i].to; if(!mark[t]&&t!=fa) getdist(t,now,d+edge[i].cost); } } int dfs(int now) { now=bestroot(now); mark[now]=true; int ret=0; for(int t,i=head[now]; i!=-1; i=edge[i].next) { t=edge[i].to; if(!mark[t]) ret+=dfs(t); } cnt=0; getdist(now,now,0); sort(temp,temp+cnt); for(int ll=0,rr=cnt-1; ll

if(temp[ll]+temp[rr]<=limit) ret-=rr-ll,ll++; else rr--; } } mark[now]=false; return ret; } /************************************/ 无向图的最大匹配 /************************************/ #include #include #include #include #include using namespace std; #define MAXE 250*250*2 #define MAXN 250 #define SET(a,b) memset(a,b,sizeof(a)) deque Q; //g[i][j]存放关系图： i,j 是否有边 ,match[i]存放 i 所匹配的点 int g[MAXN][MAXN]; bool inque[MAXN],inblossom[MAXN]; int match[MAXN],pre[MAXN],base[MAXN]; //找公共祖先 int findancestor(int u,int v) { bool inpath[MAXN]= {false}; while(1) { u=base[u]; inpath[u]=true; if(match[u]==-1)break; u=pre[match[u]]; } while(1) { v=base[v]; if(inpath[v])return v; v=pre[match[v]]; } } //压缩花 void reset(int u,int anc) { while(u!=anc) { int v=match[u]; inblossom[base[u]]=1; inblossom[base[v]]=1; v=pre[v]; if(base[v]!=anc)pre[v]=match[u]; u=v; } } void contract(int u,int v,int n) { int anc=findancestor(u,v); //SET(inblossom,0); memset(inblossom,0,sizeof(inblossom)); reset(u,anc); reset(v,anc); if(base[u]!=anc)pre[u]=v; if(base[v]!=anc)pre[v]=u; for(int i=1; i<=n; i++) if(inblossom[base[i]]) { base[i]=anc; if(!inque[i]) { Q.push_back(i); inque[i]=1; } } } bool dfs(int S,int n) { for(int i=0; i<=n; i++)pre[i]=-1,inque[i]=0,base[i]=i; Q.clear(); Q.push_back(S); inque[S]=1; while(!Q.empty()) { int u=Q.front(); Q.pop_front(); for(int v=1; v<=n; v++) { if(g[u][v]&&base[v]!=base[u]&&match[u]!=v) { if(v==S||(match[v]!=-1&&pre[match[v]]!=-1))con tract(u,v,n); 2 else if(pre[v]==-1) { pre[v]=u; if(match[v]!=-1)Q.push_back(match[v]),inque[ma tch[v]]=1; else { u=v; while(u!=-1) { v=pre[u]; int w=match[v]; match[u]=v; match[v]=u; u=w; } return true; } } } } } return false; } int maxmatch(int n) { int res=0; memset(match,-1,sizeof(match)); for(i=1; i<=n; i++) { if(match[i]==-1&&dfs(i,n)) { res++; } } return res; } /************************************/ 无向图的最大环 /************************************/ //cost:直接路径长度；dist:间接路径长度 int mincircle(){ int ans=inf; for(int k=1;k<=n;k++){ for(int i=1;i0ll&&dep[k=edge[j].y]==-1) { dep[k]=dep[i]+1; stk[rear++]=k; if(k==t) { front=rear; break; } } } }

if(dep[t]==-1) break; memcpy(cur,head,sizeof(head)); for(top=0,i=s;;) { if(i==t) { for(res=inff,k=0; kedge[stk[k]].cap) { res=edge[stk[j=k]].cap; } } flow+=res; for(k=0; k0&&dep[edge[j].y]==dep[edge[j]. x]+1) break; if(j!=-1) { stk[top++]=j; i=edge[j].y; } else { if(top==0) break; dep[i]=-1; i=edge[stk[--top]].x; } } } } return flow; } /************************************/ S ap 最大流 O（V*E*logF /************************************/ int src,sink,h[V],cur[V],num[V],n; int findpath(int x,int flow) { if(x==sink)return flow; int f=flow; for(int i=head[x]; i!=-1; i=edge[i].nxt) { if(edge[i].cap&&h[edge[i].y]+1==h[x]) { int d=findpath(edge[i].y,f > Q; dis[st] = 0; Q.push(make_pair(0, st)); while(!Q.empty()) { int u = Q.top().second, d = -Q.top().first; Q.pop(); if(dis[u] != d) continue; for(int p = head[u]; p; p = next[p]) { int &v = to[p]; if(cap[p] && dis[v] > d + cost[p]) { dis[v] = d + cost[p]; Q.push(make_pair(-dis[v], v)); } } } for(int i = 1; i <= n; ++i) dis[i] = dis[ed] - dis[i]; } int minCost, maxFlow; bool use[MAXN]; int add_flow(int u, int flow) { if(u == ed) { maxFlow += flow; minCost += dis[st] * flow; return flow; } use[u] = true; int now = flow; for(int p = head[u]; p; p = next[p]) { int &v = to[p]; if(cap[p] && !use[v] && dis[u] == dis[v] + cost[p]) { int tmp = add_flow(v, min(now, cap[p])); cap[p] -= tmp; cap[p^1] += tmp; now -= tmp; if(!now) break; } } return flow - now; } bool modify_label() { int d = INF; for(int u = 1; u <= n; ++u) if(use[u]) for(int p = head[u]; p; p = next[p]) { int &v = to[p]; if(cap[p] && !use[v]) d = min(d, dis[v] + cost[p] - dis[u]); } if(d == INF) return false;

资料库

天津大学 ACM模板.pdf

相关推荐

课程资源

热门标签

最新资料