天津大学 ACM模板

所需积分/C币:34 2018-01-25 17:43:19 2.68MB PDF

天津大学 ACM模板 本科的少年们从大二一直干到大四吧, 无怨无悔,最好的ACM模板。
图论、 //判线段相交<=:不规范相交 16 //判点在多边形内部 16 定理 //多边形内部最长线段 割点割边 //凸包对踵点长度 树的分治 //判p1,p2是否在-1,12两侧 无向图的最大匹配 //判线段在征意多边形内,顶点按顺时针 无向图的最大环 或逆时针给出,与边界相交返回1 Dinic最大浣O(v"2*) //求直线交点,必须存在交点,或者预判 5最大流O(v*E*gF 断【解析几何方法】 //求线段交点,必须存在交点,或者预判 ZkW Cost flow 断【平面几何方法】 平面图网络流 //三角形重心 合图的欧拉回路 //多边形重心 17 最大权所合图1 //求多边形面积 最大密度子图 //解方程ax^2+bx+c 最小边割集 667889 //线段与圆交点 18 二分图最小权覆盖集 /给出在任意多边形内部的一个点 最优比例生成树 //求在多边形外面的点到凸包的切点18 曼哈饭距离生成树 //判断点P在圆c内 最小原度生成树 10 //求矩形第4个点 //判两圆关系 18 次小生成树…… 11 //判圆与矩形关系,矩形水平…….18 树链剖分 11 //射线关于平面的反射 18 生成树计数 音日请4垂量垂 12 //两圆交点(预判断不相交情况)∴…18 树中删除最少边形成n连通集 13 //圆夕一点引圆的切线…19 N阶完全图生成子图数量…14 //圆e1上,与c2的外切点∴19 计算几何 14 //圆c1上,与c2的内切点 三维计算几何库… 19 公式 :::·: 14 //平面法向量 二维计草几何库 15 //判定点是否在线段上,包括端点和共线 //直线一般式转两点式 /直线两点式转一般式… 15 /判断点在平面上 /点p绕o逆时针旋转a1pha 15 //判定点是否在空间三角形上,包括边界, /向量u的倾斜角 15 三点共线无意义 /oe与os的夹角,夹角正负满足叉积15 //判定点是否在空间三角形上,不包括边 //p在1上的投影与1关系 界,三点共线无意义 //p在1上的垂足…… 15 //判定两点在线段同侧,点在线段上返回 //求点p到线段1的最短距离,并返回线 0,不共面无意义 段上距该点最近的点np. 15 /判定两点在线段异侧,点在平面上返问 //求点p到直线1的最短距离 //线段之间最短距离… //判定两点在平面同侧,点在平面上返回 //求矢量线段夹角的余弦 //求矢量的夹角的余弦… /判定两点在平面异侧,点在平面上返问 //求线段火角.… /求直线斜率 6666 判断直线平行 //直线倾斜角[0,Pi] //判定两线段相交,不包括端点和部分重 /点关于直线的对称点 16 合 /判多边形是杏逆时针 //判定线段与空间三角形相交,包括交于 //改变多边形时针顺序…16 边界和(部分)包含…20 /判定凸多边形,顶点按顺时针或逆时针 //判定线段与空间三角形相交,不包括交 给出,允许相邻边共线 ,16 于边界和(部分)包含… /判定凸多边形,顶点按顺时针或逆时针 //面面平行 给出,不允许相邻边共线 16 //判断直线垂直 20 //判点在凸多边形内或多边形边上,顶点 //面面垂直 按顺时针或逆时针给出 //判断两直线的位置关系…20 /判点在凸多边形内,顶点按顺时针或逆 //直线与平面关系 时针给出,在多边形边上返回0.…16 //线面求交 /判点在线段上 16 //线线求交 判点在线段端点左方 …16 //面面求交 //点线距离. 定积分(自适应辛普森) 36 /点面距离… 线性规划(单纳型)…156 //线线距离… 多项式乘法(FFT) /点线垂足 //已知四面体六边求体积 莫比乌斯反演(定火)…38 /四面体体积 莫比乌斯反演(例程) 38 三角形 表达式求值 凸包 21 模线性方程组 39 两凸包的最短距离 Lucas-组合数歌模 凸包的直径 快速组台数取模. 22 凸包的最大内切圆…22 整数的质因数分解…… 40 三维凸包 22 递归求等比数列之和 40 半平面交…… 最优子区间 40 23 平面最远点对……… 高精度 网格 ,24 第K个与m互质的数.142 两圆交面积 行列式计算 42 最小圆夏盖 24 排列P(n,m)最后非零位…42 单位圆覆盖最多点 25 取石子游戏 42 最小球覆盖. Nim游戏必胜方法数 4 25 圆和多边形的交 26 猜数游戏 直线关于圆的反射 26 划序数为m的最小序列 扇形的重心 28 区同最大权选歌 43 三角形内部点数…128 第n个回丈数 43 Pik公式求面积 权值最大子矩形 8 共线最多的点的个数.…9 N个点最多组成正方形个数… 29 44 N个点最多确定互不平行的直线…30 求多边形的核 30 …44 数学 30 45 数论 30 带限制的项链计数 定理与定见… 整数拆分的最大的最小公倍数.45 公式与序字列 32 46 列与组合.32 第二类斯特林数奇偶性 数学常用库 33 /°素数 数据给构 46 /欧拉函数 46 /°约数个数、最小素数次数 AC自动机…146 //脩莫比乌斯函数…. 划分树 //欧几里得…… 34 树状数组(第k大值) 47 //扩展欧几里得… 树状数组(区械维护)… //乘法逆元,【确保有逆元】….34 树状数组(约源未环) //最小公倍数 34 //数位统计,[1,con区间内数字出现次 卡尔树(Teap) 48 数 芹卡尔树2(eap)… //防高精度乘法 二又平衡树(AV) 49 34 /快速幂取模 34 KD树(空间距离前k近点)……150 //米勒拉宾伪素数测试 1垂 Sply(动态数组)…51 整数拆分… Dancing links(精磅覆盖) 52 连分数… 块状链表 5. 伯努利数 KMP 54 伯努利公式求暴方和 35 其它 54 差分序列 35 差分序列求幂方和. C+库(不常用)… 54 ..36 燥作 54 定积分(龙贝榕) ,36 关于G艹与C艹的紛入勃出 55 JAⅦ汇总 55 DP优化 着4垂日垂看,音4面看4音 56 前级等于后级的子个数 56 最长回文子 56 背包问题 基数排度 宇符环的最小表示法 最小循环矩阵 最短非了序列长度 最长下熔子序字列长度与个数 58 最少偏序集个数 58 N后问题构造方法…58 N*M数码有解判定 59 雄排序最坏憤况构造………159 图论 树的分治 问:求树中所有路径长度小于1en的点对个数 定理 InIt mark<--ta⊥se c-s (root) 部图中 定理最人匹配数等于最小覆盖数顶点属于最小覆盖集或与 bool mar k[nli 最小覆盖集中的某个页点直接相连 int temp [n], cnt, size[N] nt n,len: 最大独立集笔于最小边覆盖数最小路径覆盖泩意路径是否可重 oid getcize(in- x, int fa //以x为根的子树的 可重则还求传递闭包等于图的烹效减去最大匹配数(点数相等时) 结点数目 s1ze【x]=1 顶点的最大度数等于最小边染色数 for(int i=head [x] i!=-li i=edye[i]. llxL) 简证二部图中没有杏环对丁欧环可以用两种颜色不断重复来染色所 以只要保证最大度数点连接的边染不同色即可 int --edge[i].to if(mark[t]I It==f a) 最大团等于补图的最大独立集。建边时注意将集合分为二分图 continue get size(t, x) 最大流最小割定理 size[x]+=size[t]; 网络流图中的最大流等于最小割 平面图性质 欧拉公式)如果一个连通的平面图有个点,条边和个面,那么 nt oestroot(intx){//找树的重心 t512 每个平面图都有一个与其对偶的平面图 int half=size[x]>>1 口的每个点对应中的一个 while(1) t id=x rmax=D 对于中钓每条边 for (int i=head[x]i 属于两个面、,力入边, i=edce[⊥],next) 只属于一个面,如入问边 nt t=edge [i]to 的面数等于的点数,的点数等于 数,与边数相 if(!mark[t]&&r.max<size[t]) 同 mmax=size[i d=t]; 中的环对应中的割对应 利用最短路求最小割 if(mmax<=half) 对于一个平面怪,我们对其进行如下改造: 迕接和,得到一个附加面 size[x]-=size【ic 求该图的太偶图,令附加由对应的点为:无昇面对应的点为 size[c]+=aize【x 删去和之间的边 条从到的路径,就对应了一个割 更进一步,如果我们令每条边的长度等于它的容量,那么最小割的容 return x 量就等丁最短路的长度! 最少添加边问题 void cetcist( In now, int fa,intd)【//当首节 最少添加有向边使的原图为强连通图钓数量答丁原图缩点后出度为 点到’根的距离 的点数和入度为的点数的个数的最大值 if(d>len)retur 添加最少边彼原怪成为双连通智的效量等于原图缩点后变数为的 emp [cnt++l-d; 点加除以无向图也要缩点 for(int tr l=head[now]; 1I=-1 i=edge[i], ne xt) f t=edge[i]. toi 割点割边 iE(!mark[t]&&t!=fa) getdist(=, now, d+edge[i]. cost) nt dfa(int row) meset (vis, fal se, s-ze f(vis)) now=bes troot( ow) mem set (cnt, false 5 f(cnt) mark[ncw]=true Inent set (br -dge, Ld lse,sized(br idge)) dEs(roc tr for(int tri=head[now]ii!=-li VlS tdey【N],1ow[N]; (!mark [t1) roid dfs(int now, int fa,int deep)i ret+=dfs(t)i visLnowl=true dep [now]=low [now ]=deep; for(int i: [now]:i!=-1 i=edge[i].nxt)( t); at to=edge [i] for (int 1l=, rr=cnt-li ll<rr:)i if(tc==fa) continue if(tenr [11]+temp [rr]<=l er) se E(vis[to])low [now]=min(Icw [now], dep[tc])i else dts(tor now,deep+i): tot+十 for(int t, limit, i=head [now]; i!=-1 low [r ow]=min (low[r ow],Iow [to])i dge[i] ne xt ) t [].to if(nIk[L]) iE ((now=scot&stot>1)I(ncw!=root &&low [to]>=de continue p[]))cut[now]=true nt=D limit=len-2*edge[i].cost iE【1ow【tu]>ep[now]) ridge【i]= ori dye[-^1]=true getdist(t, t,0)i sort(temp, temp+cnt y for (int 11=3 11<rr;)( if(temp [ll]+temp[rr]<=limit) else if(pre[v]==-1)I v]=u; if(match[v]!=-1)Qpush ba ck(match [v]), in: e [ma tch[v1]=l else 1e{u!=-1) 无向图的最大匹配 matsalu]=v match【v]=u ⊥nC1 ucescst:3i> include<cstring includes cma th> return true nc⊥ce<a⊥ g or 1 thm> using name space stdi de土 i ne MAXE2>0*25Cx2 tdefine MAXN 250 tdefine SETa, b) memset(a,b, sizeof(a) return false deque<int> Q //g[11存放关系图:1,是否有边, mat chI1存放所匹 int maxmatch(int n)( 配的点 t g[MAXN]【MAxN]; memset(match,-l, size f(match)) bool inque [maXn] inb l oa son [MAXN]; for(1=1;i< 1++ -nt match[MAXN], pre[MaxN], ba se[MAXN] if(match[i]==--&&dfs(i, n))( //找公共祖先 at find ancestor (int u,int v) bool inpath[MAXN]=falser return re while(1) u=base []i inpath[u]=true if(match [u]==-1)break u= re [match [u]li 无向图的最大环 while(1)( /!cost:直接路径长度;dist:闫接路径长度 yabase【v]; int minc o)( if(inpath[v])return; v-p re [match[v]li fr(intk=1;ks=1;κ++) for(int⊥=1;i<k;i++) fox【intj=1+1;<k:j+} /压缩花 void reset (int u, int anc) i ans=min(ans, dist[i][3]+cost[i] [k]+cost[k][31)i whlle (usanc int v=match [u] nb ssom[base[u]]=l for (int i=li<=n; i++)i vapre [v]i for(int j=1j<=n;3++)i f(base[v]!=anc)pre[v]=match lu]i dist[i][i]=mir(dist[i][j],dist[-][k]+dist[k][ int anc=findancesto(u,"),( void contract (int urint v, n //SET(iIt los soll, D) return ans memset (inbloss om,0, sizeof(inb lc s som)) if(base [u]!=anc)pre [u] if(base [v]! =anc)pre[v]=u 最大流( if(inbloss n[base[i]])( base[1]=an冖 int dep[];stk【N],cux【N],pxe[时 if(!inque[i]) f l1 Dinic (int nin ) Q, puch bacκ(i); int i,3,k, top,rear,=ront inque[i]=-. l1 res while(l) t mem sat si eof【iep)) dep [stk[ front=0]=s]=0 bool dfs(int stint n)( rea==-i for(int i=0 for( -ront i=rear)[ ++)pre [i]=-l, inque [i]= base[i]=ii for【⊥=sLx【 fr ou t++],j=lead[i] Q.c⊥ear() 0!=-1 j=edge [j1. next)( g-push back(s)i ue[s]=1 if(ecge[j].cap>011kdap[k=edqe[j].y]==-1) while(! 2. empty()f dep [k]=dep [i]+1; I=k if(k==)i for (int v=; v<=:1; v+t) i f≌ont=rear; if(g[u[v]&&base[v]!=base [u]&&match [u]!=v) if (v==S II(ma tc [v]I=-l4Epre [match. [V]]!=-1))con if(dep [t]==-1) //不能有负权边,对于最终流量较大,而费用取值范围不大的 break 图,或者是增广路径比较短的图(如二分图),zkw算法都会比 memcpy(cur, head, si zeof( he ad)) 较怏 s- ruct zK t⊥w for(res=inff,k=J; k<top; k++) ±f(=s>eage[stk【k]1.cap) int cap [MAX=], cost [MAXE next[MAX三]; d t() mem set (head, 0, si ze of(read))i res=edge[stk[=kl]. cap; void addEdge (int u, int v, int cc, int ww) flow+res i for(k=0; k<top; k++)( ap [ecnt] CCH edge[stk [k]]. cap-=resi cost[ecnt]= wwi edge stk[k]l]. cap+=res next[ecnt] head[a] head[u =ecnt++ isedce [stk[top=]].i cos t[ecnt] = -Nw: for(i=cur[i]ii!=-1 lEant j=cur[i]=ecae[i]. nex=) next[ecnt head[v]i head[v]= ecnt++: if (edge [j].cap>0&&dep[edge[j]. y]==den[edge [3] int dis [MAXn]i x]+1) void SPEA(】 break for(int⊥ ,i<= n: ++i) cis [i] i(j!=-1) TNF stk [top++]=i; priorty queue<pairsint, inL>>Q =edge[j] die [st] t else 2. push (make pa=r(o, st))i if(t⊙p==0) while(!Qempty())( break der[i]=-1 -Q.tcp(}· fir st i=edge [s tk[--top]].x 2.pop()i if(dis[u] ! d) continue for(int p =Fead [u]; p: p= next [p]) toLl return f1。w; f(cap[p]巫dis[vl>d+ cost[p]】 dis [vl [pl 最大流( 2. push(make pair(-disLvI, v)) -nt src sink, h[v], cur [v], num[v], ni ath(inr tnt fl nw) t if(x=sink)return flowi for (int i < n: ++i) cis [i] =dis【ec]-dis【i] for(int i=read[x]ii!=-li i=edge[i]. nxt)t f(ecge[i]. cap&&h[edge[i] y]+I==h[x]) int mincost, max Elow; bool use [MAXN] int add fl ow(int nt f1ow)( d=findp ath(edge [i] y, f<edge[il. cap?=:edge[i].c if(u ed)i edge [1]. cap-=d: mirCost + dis [st]* flo if(h[src]==n|!f)return fl ow-f [u】=txue nt nc w=⊥ow for(int p= lead [u]: F; p=next[pI irt minher for(int i=heac[x]=cur[xI i!=-1 to[pl =edge【1].rxt) ( capp&!use[v」a1s[u t[E]) f(edge [i]. cap&&h ledge [i] y]+l<minh)m:nh=h [edg iat tmp add flow(y, nmin(now e[i].y]+1 cap[p])】; cap[r] - trp if(num[h[x]]-1=n)h[src]=n else h[x]=minh return fle if(! now) breaki memcpy(cur, head, sizeof(head))i return flcw n memset(h,0, sizeof(h))i memset(num,U, sizeof(num)) boo⊥ modify⊥abe⊥() n[0]=1 d nt d NF irt ans=J for (int u=liu<=ni ++u)if(useful) while(h [arc] <n)ans+=findpath(arc,inf) for(int p= head[u]i pi p return ans next [p])( int &v= to[p]i iE(cap[pla&!usev]】d min (d, dis [v]+ cost[p]- dis [u])i if( NF) return false For (int i =ii<= n; ++i) ifluselil 3[i]+=d; return true ang=atan2 ((double)(ro[al. y-po[b] y),(double)(p o[a].x-po[].x)); irt min cos- =low(in- ss, int t=, int nn) vector< Poi nt Ar g1e>1re[NAx]://入边编号 void cdc d (int d,int b, 11 c)( edge d[ne d]. tosb i Imlin Ccst inax Flow = C edge d[nc d] cost=ci age d[nc d].nxt=he ad d[a] while( true) I ledd d[a]=nIc d++ while(true) t use[il= D edge t[nc f].pa=a if(! add flow(s-, INE)) dge f[nc E].pb=bi edge f[nc f] cost=ci if(! mod:fy l abel())break in e [h]. PR(Poi nt Angle(a, b, nc f))i return mi rccs void ini tot emset (head d sizeof(head d)) mmleluset (head 1, sizeof(head f))i for(int i=0i i<MAX i++)in e[i]. clear oi 平面图网络流 void work(nt id inc⊥1ce<cstd1 sort (in e[id]. begin(),in elic I erd()) ⊥nC1ue<cstr1:1g> for (int i=o;i<si-li1++) 半inc1uce< algorithm> finclucesvector> edge f[i_e【icl[i1.e].nxt=ine[dl【a+11.e^1 inc⊥ue< cma th> tdefine Me make pair define PB pus n back define x王irst ge±[ elid]【s1-1].el.nx=ine[id] tdefine y second using name space std Ld make pcint (int e, int id)[ typedef lcnc long ll E。r(int const in- MAX=:00005,INF=0x3f3-3f3f i=e:i!=-l&&pres [i]==-l;i=edge t[i]. nxt) const 1l INFC=ILL<<6D pres[-]=id; n t he ad d[Mx], head f[M],ncc,ncf;//最短路径 1 spfa(int src, int sink)( =0; i<n d:i++)dist[i]=INF'Ci 最大流 seS )) d,Sa,nd;//流的 at【a s,T以及与之关联的边和最短路的S,T front=O nt rres[MA×]://每条边右方代表的最短路中的点 rear= 1aist[vAx]:/最短路径度 i(1【src]=t bool in q[MAX] int now, to nt Ls [MAX] front reari COSti struct point! whLe【tron-!=rea=) in g[ncw=Ls[fror t++]]=false irt X, yi void adot if(ront=sMAX)front=oi scanf("dad",&x, &y)i =head d[now];i!=-;i=edge d[i]. nxt) hool opera tor<(cons- po i nt &ne)ccnst( o=edge d[i]to; 工etu工nx<Ie,x cost=edge d[il, cost+dist[ncw] iE(diat[=o]>ccst)【 pinto( dist [to]=cos pont〔tnt×,inty) if(in q[to])( in g[-s [rear+]=to]=true if(rear==MAX)rear=o ypo[MAXIi trucK EdyeD-st t irt to,nx } edge d[凶AX*3] return cist[sin k] struct EdgeF-cw i int pa, pb, nxt int maino int Test,3,o y edge f [MAX*.] sTruct PointAIIglet for(scanf("d",&Test); Tesi; Ie st--) t double anc i scanf ( dsd", &n f, &m f) s f-r f-1 bool operator<(const PointAnlgle &1e)consT for (int i= 1<=n t return anc<ne.ang; [i] PointEr. g⊥e()U i(p°[土]4o[1])It=i; pcintArgle(int a, int b,int e)i for (int i=0; 1<m fi 1++)1 scanf("ids de I64c", &a, &b,&c); f(a==o)continue; adc f(a,b, c) l, po[s f] v ),R(pC tf(bf[pa【k]].c≤tr) p[0]=L p°[ add f(n,s f,TNFC) add f(s f,0, INFC) for(K=0;k<t。p;k++) addt(n土+⊥T土,IEC bt lps [k]], c-=tr, bf[es[k]nl]. c+=tr add f(T f, Il E+l, IN FC)i for (int i=ii<=n f;++)work(i) memset(pres,-1, sizeof(pre s))i make po=nt (s e,U) for (j=cur[i]icur[i]j=cur [i]=bt[cur [i]]. nxt) make point( e, 1) t d= if (bf[j].c&&dep[i]+1==dep [bf[i] y]) break for (int i=o;i<nc E;i++)i if(pres [i]==-1)t if (cur[il) make point(i,r a)i n d++ ps[top++]=car[i]i r[i]] For (int i-0ii<s eii+=2)t el se add d(pes[i], pres[i l], edge f[i].cost) if(C==LOp) break dep[i]=-lii=bf [pc[--tor]].i addd(ys【i^1],pres[i],e山g绝【i].C0st); print=(I6d\n,epfa(s d,t d) return res: retu工n0 混合图的欧拉回路 while(nun-- inc⊥1ce< stoic> scanf (eded", &n, &m ⊥nC1ue<Cstr⊥:1gy> .emset(d,C, sizeof(d))i using namespace std remset(head,0, sizeof (he ad))i nt hile( m--) d[300],ne,head[300],cur[3001,ps[001,dep[3001; Cd「("8d3d3d",c,岳b,s); if(E==1) bf[20C00] d[a]-- const int inf=1<<297 d[b] bE[ne]. x=x; bf[e]y=yi bf [ne l bf[nel nx t=head[x]head[x]=e++; dd(a, b,1) bf[ne]. x=yibf[ne]y=ibf [ne]. c=0 d[a]--;c[b]++ bf[nel nxt=head[y]; head[Yl=ne++i int tr, res=0,1,j,k,f,r,top; EoE【i=1;i<=n;i++ f([1]<) mer.set(dep, -l, sizeof( de p))i f((-d[i])82!=0 for(f=dep[ps[0]=s]=0, r=lf!=r:) flag=false break for(i=ps[f++],shead[i]i]i=bf[j]. nxt) f(bE[j] =dep [k=bI[']y]) (,,-[1] e+=-d[i]!2 dep Ik]=dep [i]+I;ps[r++l=<; if(k==t) else f(c[i]82!=3) flay=false; break iE(-1==dp[t]) Is break (cur, head, n*sizeof(int) add(i, n+l, d[i1/2) for( 1(1==-) C,n+1)) prim=f("pcssible\n")

...展开详情
试读 64P 天津大学 ACM模板
img
mandagod

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    天津大学 ACM模板 34积分/C币 立即下载
    1/64
    天津大学 ACM模板第1页
    天津大学 ACM模板第2页
    天津大学 ACM模板第3页
    天津大学 ACM模板第4页
    天津大学 ACM模板第5页
    天津大学 ACM模板第6页
    天津大学 ACM模板第7页
    天津大学 ACM模板第8页
    天津大学 ACM模板第9页
    天津大学 ACM模板第10页
    天津大学 ACM模板第11页
    天津大学 ACM模板第12页
    天津大学 ACM模板第13页
    天津大学 ACM模板第14页
    天津大学 ACM模板第15页
    天津大学 ACM模板第16页
    天津大学 ACM模板第17页
    天津大学 ACM模板第18页
    天津大学 ACM模板第19页
    天津大学 ACM模板第20页

    试读已结束,剩余44页未读...

    34积分/C币 立即下载 >