浙江大学ACM模板
7.1无向图关键点(ds邻接阵) 77 72无向图关键边(df邻接阵) 78 73无向图的块(bts邻接阵)… 74无向图连通分支(dfs/bf邻接阵) 75有向图强连通分支( dfs bfs邻接阵)… 8 76有向图最小点基(邻接阵) 82 图论匹配83 8.1二分图最大匹配( hungary邻接表). 8.2分图最大匹配( hungary邻接阵) 84 8.3二分图最大匹[ hungary正向表) 84 84二分图最佳兀配( kuhn munkras邻接阵)85 8.5一般图匹配(邻接表) 86一般图匹配(邻接阵) 87 8.7一般图匹配(正向表) 87 …图论—网络流88 9最大流(接阵) 8 9.2上下界最大流(邻接) 9.3上下界最小流(邻接阵) 94最大流无流量(邻接阵)… 91 9.5最小费用最人流(邻接阵) 10 图论一应用92 01欧拉回路(邻接阵)... 92 102树的前序表转化 · 93 10.3树的优化算法 10.4拓扑排序(邻接阵) ···+·:· 95 10.5最佳边割集 96 10.6最佳点割集 97 107最小边割集 10.8最小点割集 10.9最小烙径覆盖. 10 图论—支撑树101 1.1最小生成树( kruskal邻接表) 101 112最小生成树( kruskal正向表) ……103 113最小生成树(prm+ binary hcap邻接表) 114最小生成树(pim+ binary heap正向表) ……105 115最小生成树(prim+ mapped heap邻接表)… 106 16最小生成树(prim+ mapped heap正向表)… 108 117最小生成树prim邻接阵)… 109 118最小树形图(邻接阵)… 12 图论最短路径111 12.I最短路径(单源 bellman ford邻接阼)… III 12.2最短路径(单源 dijkstra+bs邻接表) 12.3最短路径(单源 dijkstra+bs正向表) 112 124最短路径(单源 dijkstra+binary hcap邻接表) 113 12.5最短路径(单源 dijkstra- binary heap正向表) 114 12.6最短路径(单源 dijkstra+ mapped heap邻接表)15 12.7最短路径(单源 dijkstra mapped heap正向表) 116 12.8最短路径(单源 dijkstra令接阵).… …117 12.9最短路径(多源 floyd warshall邻接阵) 18 13 应用118 13.1 Joseph问题 118 13.2N皇后构造解. 。,( 119 133布尔母函数 120 13.4第k元素. .120 13.5幻方构造 …121 13.6模式匹配(kmp) 122 13.7逆序对数 ……………123 13.8字符串最小表示 123 13.9最长公共单调子序列 4·+“++ 124 13.10最长子序列 ··c 125 13.11最大子串匹配 126 13.12最大了段和127 13.13最人子阵和. ·,, .127 其它 128 141大数(只能处理正数) 128 142分数 134 143矩阵… 144线性方程组 138 14.5线性相关 ..140 14.6日期. 140 1、几何 1.1注意 1.注意舍入方式(0.5的舍入方向);防止输出-0 2.几何题注意多测试不对称数据 3.整数几何注意 xmult和 dmult是否会出界; 符点几何注意eps的使用 4.避免使用斜率;注意除数是否公为0 5.公式一定要化简后再代入 6.判断同一个2*P域内两角度差应该是 abs(al-a2)beta labs(al-a2)>pi+pi-beta; 相等应该是 abs(al-a2)eps labs(al-a2p>pit pi-eps; 7.需要的话尽量使用atan2,注意:atan2(0,0)-0, atan2(1,0)pi/2,atan2(-1,0)=pi/2,atan2(0,1)=0,atan2(0,-1)=pi 8. cross product =u *v*sin(a) dot product=u *v *cos(a) 9(P1-PO)x(P2-PO)结果的意义 正:<PO,P1>在<PO,P2>顺时针(0pi)内 负:<PO,P1>在<PO,P2>逆时针(0,pi)内 0:<PO,P1>,POP2>共线,夹角为0或pi 10.误差限缺省使用1e-8! 12几何公式 三角形 1.半周长P=(a+b+c)2 2.面积S=aHa/2= absin(C)2=sqrt(P(P-a)Pb)Pc) 3. f Ma=sqrt(2(b 2+c/2)-a2)/2=sqrt(b2+ c 2+ 2bCcos(A),2 4.角平分线Ta=sqr(bc(b+c)^2a^2)(b+c)=2bcos(A2)(b+c) 5.1 Ha=bsin(C)=csin(B)=sqrt(b/ 2-((a 2+b 2-c/2)(2a)2) 6.内切圆半径rSP=asin(B/2)sin(C/2/sin(B+C)/2) 4Rsin(A/2)sin(B/2)sin(C/2)=sqrt(P-a)(P-b)(P-c)/P) =Ptan(A/2)tan(B/)tan(C/2) 7.外接圆半径R=abc(4S)=a(2sin(A)=b/(2sin(B)=c/(2sin(C) 四边形 D1,D2为对角线,M对角线中点连线A为对角线夹角 1.a^2+b^2+c^2+d^2=D1^2+12^2+4M^2 2. S=DID2sin(A)/2 (以下对圆的内接四边形) 3. ac+bd=DID2 4S-sqr(P-a)(P-b)(Pc)(P-d),P为半周长 正n边形: R为外接圆半径r为内切圆半径 1.中心角A-2PIn 2.内角C-n-2)PIn 3. it a=2sqrt(R/2-r"2)=2Rsin(A/2)=2rtan (A/2) 4. TAtA S-nar/2-nr 2tan(A/2)=nRA2sin(A)/2=na 2/ (4Lan(A/2) 员 弧长1rA 2.弦长a=2sqrt(2hrh^2)=2rin(A/2) 3.弓形高h-qr(r42-a2/4)r(1-cos(A2)=aan(A4)2 4.扇形面积S1-rl2-r^2A 5.弓形面积S2-(rl-a(r-h)2=r^2(A-sin(A)/2 棱柱: 1.体积V=Ah,A为底面积h为高 2.侧面积S-lp,为棱长,p为直截面周长 3.全面积T=S+2A 棱锥: 1.体积V=Ah3,A为底面积,h为高 (以下对正棱锥) 2侧面积S=p/2,为斜高p为底面周长 3.全面积T=S+A 棱台 1.体积V=(A1+A2-sqr(AA2)h3,A1A2为上下底面积h为高 (以下为正棱台) 2侧面积S=(pl+p2川/2pp2为上下底面周长为斜高 3.全面积TS+A1+A2 圆柱: 1.侧面积S=2PIrh 2.全面积T=2PIh+r) 3.体积V=PIr^2h 园锥 1.母线lsqr(h^2+r^2) 2.侧面积S=PIrl 3.全面积T=PIr(+r) 4.体积VPIr^2h3 园台 母线1=qrth^2+(r12)^2) 2.侧面积S-PI(r1+r2 3.全面积T-Plr1(+r1)+PIr2(+r2) 4.体积V=PI(r1^2r2^2Hrlr2h/3 球 1.全面积T=4PIr^2 2.体积V-4PIr^3/3 球台: 1.侧面积S=2PIrh 2.全面积T=Pl(2h+r1^2+r2^2) 3.体积V=PIh(3(r142+r2^2)+h^2)6 球扇 1.全面积T-Plr(2h+r0),h为球冠高,r0为球冠底面半径 2.体积V=2PIr^2h/3 13多边形 #includc <stdlib. h> #include <math. h> #define maxn 1000 #define offset 10000 #define eps le-8 #dcfinc zero(x)(((x)>0? (x) -(x))<cps) +define sign(x)((x)>eps? 1: ((x<-eps? 2: 0)) struct point(double x, y; 3 struct lineipoint a, b: 1 doublc xmult(point pl, point p2, point po)i return(pl x-PO. x)*(p2.y-pO y)-(p2x-pO. x *(pl.y-pOy /判定凸多边形顶点按顺时针或逆时针给出,允许相邻边共线 int is convex(int n, point p)i inti,s[3]={1,1,1}: for(i=0;<n&&S[l][2]i++) s sign(xmult(p[(i+l)%on l pl(i-2)%)l return s[1]s[2]: 判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线 int is convex v2(int n, point p)i inti,s[3}={1,1,1}; for(i=0<n&&S[0&&[l]ls[2];i++) s[ sign(mull([(i+1)%n] p[(i-2)%n]pliD=0 return s[o]&&s[1s[2]; /)点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出 int inside convex( point q, int n, point p)i inti,s[3]{1,1,1}; for(i=0i<n&&s[l]s[2];i++) s[ sign(muli(p[(i+1)%n, pli=0 rcturn s[1s[2 /判点在凸多边形内顶点按顺时针或逆时针给出,在多边形边上返回0 int inside convex v2(point g, int n, point* p)i inti,s[3}{1,1,1}; for(i-0;i<n&&s[O]&&s[1s2]i++) s[ sign(xmult(pl(i+1)%n], a, piD]=0; rcturn s[o]&&s[1]s[2]: /判点在任意多边形内,顶点按顺时针或逆时针给出 on edge表示点在多边形边上时的返回值, offset为多边形坐标上限 int insidc polygon(point q, int n, point, int on cdgc=D)& point q2, int io.count. for(count=i-0. q 2. x=rando+offset, q2. y=rando-offset i<n; i++) (cro(xmut(qp[]p(+1)%n])&&(p[i]x-qx)*(p[(+1)9n]x-q1x)<cps&&(p[]y-qy)*(p[(+1n]y g y<eps) return on edge else if (zero(xmult(, q2,pi) break if (xmult(q,pl], q2)*xmult(a, p[(i+1)%n], q2) eps&&xmult(p[l, a,pl(i+l)%on*xmult(pi, q2,pl(i+)%on < -eps) count++ return count l inline int opposite side(point pl, point p2, point 11, point 12)1 return xmult(l, pl, 12)*xmult(ll, p2, 2 <-eps lline int dot online in(point p, point ll, point 12)i return zero(xmult(p, 11, 12)&&(1. x-p. x) *(12 x-p.x)<eps&&(ll.y-p y)*(12 y-p y)<eps; ∥判线段在任意多边形内顶点按顺时针或逆时针给出,与边界相交返回1 int inside polygon(point l1, point 12, int n, point p)i point tIMAXN], tt; if (inside polygon(ll, n, p) inside polygon(12, n,p)) rcturn for(i=0; i <n; 1++) if (opposite side(1, 12, pi],pl(i+1)%n])&&opposite side(pil, pl(i+1)%n), 11, 12)) eturn o else if(dot online in(ll,pli] p[(i+1)%n])) t[k++]=1 else if (dot online in(12, pi,pl(i+l)%nD)) t[k++]12 else if (dot online in(p[i], ll, 12)) 1[k++]pi for(-0;i<k;i++) for (j=i+:j<k;j++) t(t(i].x+tj].x)/2; tt.y=(t[i]y+tu].-y)/2; if(inside polygon(l, n, p)) return o return 1 point intersection(line u, line v)( point ret=ua double t=((u a x-v.ax)(v. a y-v.b y)-(u ay-v. ay)*(v.ax-v.b x)) /((uax-u.b x *(v. a y-v.b y)-(uay-u. b y)*(v.ax-v.bx)); ret x+=(ub x-u.ax)*t; ret y+=(uby-u.ay)"t; return ret point barycenter(point a point b, point c)i line uv uax=(ax+b x)/2; uy=(a.y+b.y)/2;