ACM經(jīng)典試題集華師大

1目錄一數(shù)論31階乘最后非零位32模線性方程組43素數(shù)表54素數(shù)隨機判定MILLER_RABIN65質(zhì)因數(shù)分解66最大公約數(shù)歐拉函數(shù)8二圖論_匹配91二分圖最大匹配HUNGARY鄰接表形式92二分圖最大匹配HUNGARY鄰接表形式,鄰接陣接口93二分圖最大匹配HUNGARY鄰接陣形式104二分圖最大匹配HUNGARY正向表形式105二分圖最佳匹配KUHN_MUNKRAS鄰接陣形式116一般圖匹配鄰接表形式127一般圖匹配鄰接表形式,鄰接陣接口138一般圖匹配鄰接陣形式149一般圖匹配正向表形式14三圖論_生成樹151最小生成樹KRUSKAL鄰接表形式152最小生成樹KRUSKAL正向表形式173最小生成樹PRIMBINARY_HEAP鄰接表形式184最小生成樹PRIMBINARY_HEAP正向表形式195最小生成樹PRIMMAPPED_HEAP鄰接表形式206最小生成樹PRIMMAPPED_HEAP正向表形式217最小生成樹PRIM鄰接陣形式228最小樹形圖鄰接陣形式23四圖論_網(wǎng)絡流241上下界最大流鄰接表形式242上下界最大流鄰接陣形式263上下界最小流鄰接表形式274上下界最小流鄰接陣形式285最大流鄰接表形式296最大流鄰接表形式,鄰接陣接口307最大流鄰接陣形式318最大流無流量鄰接陣形式319最小費用最大流鄰接陣形式32五圖論_最短路徑331最短路徑單源BELLMAN_FORD鄰接陣形式332最短路徑單源DIJKSTRA_BFS鄰接表形式343最短路徑單源DIJKSTRA_BFS正向表形式344最短路徑單源DIJKSTRABINARY_HEAP鄰接表形式355最短路徑單源DIJKSTRABINARY_HEAP正向表形式366最短路徑單源DIJKSTRAMAPPED_HEAP鄰接表形式3727最短路徑單源DIJKSTRAMAPPED_HEAP正向表形式388最短路徑單源DIJKSTRA鄰接陣形式399最短路徑多源FLOYD_WARSHALL鄰接陣形式39六圖論_連通性401無向圖關鍵邊DFS鄰接陣形式402無向圖關鍵點DFS鄰接陣形式413無向圖塊BFS鄰接陣形式424無向圖連通分支BFS鄰接陣形式425無向圖連通分支DFS鄰接陣形式436有向圖強連通分支BFS鄰接陣形式437有向圖強連通分支DFS鄰接陣形式448有向圖最小點基鄰接陣形式45七圖論_應用451歐拉回路鄰接陣形式452前序表轉(zhuǎn)化463樹的優(yōu)化算法474拓撲排序鄰接陣形式485最佳邊割集496最佳頂點割集507最小邊割集518最小頂點割集529最小路徑覆蓋53八圖論_NP搜索541最大團N小于64FASTER542最大團56九組合571排列組合生成572生成GRAY碼593置換POLYA594字典序全排列605字典序組合606組合公式61十數(shù)值計算611定積分計算ROMBERG612多項式求根牛頓法633周期性方程追趕法64十一幾何651多邊形652多邊形切割683浮點函數(shù)694幾何公式745面積766球面777三角形7738三維幾何809凸包GRAHAM8710網(wǎng)格PICK9011圓9012整數(shù)函數(shù)9213注意95十二結構951并查集952并查集擴展FRIEND_ENEMY963堆BINARY964堆MAPPED975矩形切割986線段樹987線段樹擴展1008線段樹應用1039子段和10310子陣和103十三其他1041分數(shù)1042矩陣1063日期1084線性方程組GAUSS1095線性相關111十四應用1121JOSEPH1122N皇后構造解1123布爾母函數(shù)1134第K元素1145幻方構造1146模式匹配KMP1157逆序?qū)?shù)1168字符串最小表示1169最長公共單調(diào)子序列11710最長子序列11811最大子串匹配11912最大子段和12013最大子陣和120一數(shù)論1階乘最后非零位/求階乘最后非零位,復雜度ONLOGN/返回該位,N以字符串方式傳入INCLUDEDEFINEMAXN100004INTLASTDIGITCHARBUFCONSTINTMOD201,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2INTLENSTRLENBUF,AMAXN,I,C,RET1IFLEN1RETURNMODBUF00FORI0I0ICC10AI,AIC/5,C5RETURNRETRET252模線性方程組IFDEFWIN32TYPEDEF_INT64I64ELSETYPEDEFLONGLONGI64ENDIF/擴展EUCLID求解GCDA,BAXBYINTEXT_GCDINTA,INTB,INTIFBX1,Y0RETURNARETEXT_GCDB,AB,X,YTX,XY,YTA/BYRETURNRET/計算MA,OLOGA,本身沒什么用,注意這個按位處理的方法PINTEXPONENTINTM,INTAINTRET1FORAA1,MMIFARETURNRET/計算冪取模ABMODN,OLOGBINTMODULAR_EXPONENTINTA,INTB,INTN/ABMODN5INTRET1FORBB1,AINTI64AANIFBRETURNRET/求解模線性方程AXBMODN/返回解的個數(shù),解保存在SOL中/要求N0,解的范圍0N1INTMODULAR_LINEARINTA,INTB,INTN,INTSOLINTD,E,X,Y,IDEXT_GCDA,N,X,YIFBDRETURN0EXB/DNNNFORI0I0,WI與WJ互質(zhì),解的范圍1N,NW0W1WK1INTMODULAR_LINEAR_SYSTEMINTB,INTW,INTKINTD,X,Y,A0,M,N1,IFORI0I1VOIDINITPRIMEINTIFORPLISTPCOUNT2,I3IIFDEFWIN32TYPEDEF_INT64I64ELSETYPEDEFLONGLONGI64ENDIFINTMODULAR_EXPONENTINTA,INTB,INTN/ABMODNINTRETFORBB1,AINTI64AANIFBRETURNRET/CARMICHEALNUMBER561,41041,825265,321197185INTMILLER_RABININTN,INTTIME10IFN1|N2WHILETIMEIFMODULAR_EXPONENTRANDDEFINEMAXN2001000DEFINEPSIZE100000INTPLISTPSIZE,PCOUNT0INTPRIMEINTNINTIIFN2FORI0PLISTIPLISTI1VOIDINITPRIMEINTIFORPLISTPCOUNT2,I3I1RETURNCNT/產(chǎn)生MAXN以內(nèi)的所有素數(shù)/NOTE2863311530就是10101010101010101010101010101010/給所有2的倍數(shù)賦初值8INCLUDEINCLUDEUSINGNAMESPACESTDDEFINEMAXN100000000UNSIGNEDINTPLIST6000000,PCOUNTUNSIGNEDINTISPRIMEMAXN51DEFINESETBITZEROAISPRIMEA5FORI0I1RETN1RETURNRET9二圖論_匹配1二分圖最大匹配HUNGARY鄰接表形式/二分圖最大匹配,HUNGARY算法,鄰接表形式,復雜度OME/返回最大匹配數(shù),傳入二分圖大小M,N和鄰接表LIST只需一邊/MATCH1,MATCH2返回一個最大匹配,未匹配頂點MATCH值為1INCLUDEDEFINEMAXN310DEFINE_CLRXMEMSETX,0XFF,SIZEOFINTMAXNSTRUCTEDGE_TINTFROM,TOEDGE_TNEXTINTHUNGARYINTM,INTN,EDGE_TLIST,INTMATCH1,INTMATCH2INTSMAXN,TMAXN,P,Q,RET0,I,J,KEDGE_TEFOR_CLRMATCH1,_CLRMATCH2,I0I0FOR_CLRT,SPQ0IPNEXTIFTJETO0JPMATCH2JKTJ,PMATCH1K,MATCH1KJRETURNRET2二分圖最大匹配HUNGARY鄰接表形式,鄰接陣接口/二分圖最大匹配,HUNGARY算法,鄰接表形式,鄰接陣接口,復雜度OMES/返回最大匹配數(shù),傳入二分圖大小M,N和鄰接陣/MATCH1,MATCH2返回一個最大匹配,未匹配頂點MATCH值為1INCLUDEINCLUDEDEFINEMAXN310DEFINE_CLRXMEMSETX,0XFF,SIZEOFINTMAXNINTHUNGARYINTM,INTN,INTMATMAXN,INTMATCH1,INTMATCH2INTSMAXN,TMAXN,P,Q,RET0,I,J,K,RVECTOREMAXN/生成鄰接表只需一邊FORI0I010FOR_CLRT,SPQ0IP0JPMATCH2JKTJ,PMATCH1K,MATCH1KJRETURNRET3二分圖最大匹配HUNGARY鄰接陣形式/二分圖最大匹配,HUNGARY算法,鄰接陣形式,復雜度OMMN/返回最大匹配數(shù),傳入二分圖大小M,N和鄰接陣MAT,非零元素表示有邊/MATCH1,MATCH2返回一個最大匹配,未匹配頂點MATCH值為1INCLUDEDEFINEMAXN310DEFINE_CLRXMEMSETX,0XFF,SIZEOFINTMAXNINTHUNGARYINTM,INTN,INTMATMAXN,INTMATCH1,INTMATCH2INTSMAXN,TMAXN,P,Q,RET0,I,J,KFOR_CLRMATCH1,_CLRMATCH2,I0I0FOR_CLRT,SPQ0IP0JPMATCH2JKTJ,PMATCH1K,MATCH1KJRETURNRET4二分圖最大匹配HUNGARY正向表形式/二分圖最大匹配,HUNGARY算法,正向表形式,復雜度OME/返回最大匹配數(shù),傳入二分圖大小M,N和正向表LIST,BUF只需一邊/MATCH1,MATCH2返回一個最大匹配,未匹配頂點MATCH值為1INCLUDEDEFINEMAXN310DEFINE_CLRXMEMSETX,0XFF,SIZEOFINTMAXNINTHUNGARYINTM,INTN,INTLIST,INTBUF,INTMATCH1,INTMATCH2INTSMAXN,TMAXN,P,Q,RET0,I,J,K,LFOR_CLRMATCH1,_CLRMATCH2,I0I0FOR_CLRT,SPQ0IP0JPMATCH2JKTJ,PMATCH1K,MATCH1KJRETURNRET5二分圖最佳匹配KUHN_MUNKRAS鄰接陣形式/二分圖最佳匹配,KUHNMUNKRAS算法,鄰接陣形式,復雜度OMMN/返回最佳匹配值,傳入二分圖大小M,N和鄰接陣MAT,表示權值/MATCH1,MATCH2返回一個最佳匹配,未匹配頂點MATCH值為1/一定注意MDEFINEMAXN310DEFINEINF1000000000DEFINE_CLRXMEMSETX,0XFF,SIZEOFINTNINTKUHN_MUNKRASINTM,INTN,INTMATMAXN,INTMATCH1,INTMATCH2INTSMAXN,TMAXN,L1MAXN,L2MAXN,P,Q,RET0,I,J,KFORI0IL1IMATIJL1IFORI0I0JPMATCH2JKTJ,PMATCH1K,MATCH1KJIFMATCH1INEXTIFVTETOIFMATCHT2IFMATCHI013RETURNJ/27一般圖匹配鄰接表形式,鄰接陣接口/一般圖最大匹配,鄰接表形式,復雜度ONE/返回匹配頂點對數(shù),MATCH返回匹配,未匹配頂點MATCH值為1/傳入圖的頂點數(shù)N和鄰接表LISTINCLUDEDEFINEMAXN100INTAUGINTN,VECTORLIST,INTMATCH,INTV,INTNOWINTT,RET0,RVNOW1/FORELISTNOWEEENEXTFORR0RLISTMAXNFORI0I2IFMATCHI0RETURNJ/28一般圖匹配鄰接陣形式/一般圖最大匹配,鄰接陣形式,復雜度ON3/返回匹配頂點對數(shù),MATCH返回匹配,未匹配頂點MATCH值為1/傳入圖的頂點數(shù)N和鄰接陣MATDEFINEMAXN100INTAUGINTN,INTMATMAXN,INTMATCH,INTV,INTNOWINTI,RET0VNOW1FORI0I2IFMATCHI0RETURNJ/29一般圖匹配正向表形式/一般圖最大匹配,正向表形式,復雜度ONE15/返回匹配頂點對數(shù),MATCH返回匹配,未匹配頂點MATCH值為1/傳入圖的頂點數(shù)N和正向表LIST,BUFDEFINEMAXN100INTAUGINTN,INTLIST,INTBUF,INTMATCH,INTV,INTNOWINTI,T,RET0VNOW1FORILISTNOWI2IFMATCHI0RETURNJ/2三圖論_生成樹1最小生成樹KRUSKAL鄰接表形式/無向圖最小生成樹,KRUSKAL算法,鄰接表形式,復雜度OMLOGM/返回最小生成樹的長度,傳入圖的大小N和鄰接表LIST/可更改邊權的類型,EDGE2返回樹的構造,用邊集表示/如果圖不連通,則對各連通分支構造最小生成樹,返回總長度INCLUDE16DEFINEMAXN200DEFINEINF1000000000TYPEDEFDOUBLEELEM_TSTRUCTEDGE_TINTFROM,TOELEM_TLENEDGE_TNEXTDEFINE_UFIND_RUNXFORPTXXPX,PTPXPXXDEFINE_RUN_BOTH_UFIND_RUNI_UFIND_RUNJSTRUCTUFINDINTPMAXN,TVOIDINITMEMSETP,0,SIZEOFPVOIDSET_FRIENDINTI,INTJ_RUN_BOTHPIIJ0JINTIS_FRIENDINTI,INTJ_RUN_BOTHRETURNIJDEFINE_CPA,BALEN1HPHP1,P1HPEINTDELHEAP_TFOREHP1,C2CNEXTIFITO17EAI,EBTTO,ELENTLEN,HINSEWHILEMDEFINEMAXN200DEFINEINF1000000000TYPEDEFDOUBLEELEM_TSTRUCTEDGE_TINTTOELEM_TLENDEFINE_UFIND_RUNXFORPTXXPX,PTPXPXXDEFINE_RUN_BOTH_UFIND_RUNI_UFIND_RUNJSTRUCTUFINDINTPMAXN,TVOIDINITMEMSETP,0,SIZEOFPVOIDSET_FRIENDINTI,INTJ_RUN_BOTHPIIJ0JINTIS_FRIENDINTI,INTJ_RUN_BOTHRETURNIJDEFINE_CPA,BALEN1HPHP1,P1HPEINTDELHEAP_TFOREHP1,C2C1HPHP1,P1HPEINTDELHEAP_TFOR19EHP1,C2CNEXTIFVTTORETURNRET4最小生成樹PRIMBINARY_HEAP正向表形式/無向圖最小生成樹,PRIM算法二分堆,正向表形式,復雜度OMLOGM/返回最小生成樹的長度,傳入圖的大小N和正向表LIST,BUF/可更改邊權的類型,PRE返回樹的構造,用父結點表示,根節(jié)點第一個PRE值為1/必須保證圖的連通的DEFINEMAXN200DEFINEINF1000000000TYPEDEFDOUBLEELEM_TSTRUCTEDGE_TINTTOELEM_TLENDEFINE_CPA,BAD1HPHP1,P1HPEINTDELHEAP_TFOREHP1,C2C1HMAPINDPINDP1PHP1,P1HMAPINDPIPE21INTDELINTI,ELEM_TIFINRETURN0FOREHPIP1HMAPINDPINDP1PHP1,P1FORC2CNEXTIFVTTORETURNRET6最小生成樹PRIMMAPPED_HEAP正向表形式/無向圖最小生成樹,PRIM算法映射二分堆,正向表形式,復雜度OMLOGN/返回最小生成樹的長度,傳入圖的大小N和正向表LIST,BUF/可更改邊權的類型,PRE返回樹的構造,用父結點表示,根節(jié)點第一個PRE值為1/必須保證圖的連通的DEFINEMAXN200DEFINEINF1000000000TYPEDEFDOUBLEELEM_TSTRUCTEDGE_TINTTOELEM_TLENDEFINE_CPA,BA1HMAPINDPINDP1PHP1,P1HMAPINDPIPEINTDELINTI,ELEM_TIFINRETURN0FOREHPIP1HMAPINDPINDP1PHP1,P1FORC2CDEFINEMAXN120DEFINEINF1000000000TYPEDEFINTELEM_TELEM_TEDMONDSINTN,ELEM_TMATMAXN2,INTPREELEM_TRET0INTCMAXN2MAXN2,LMAXN2,PMAXN2,MN,T,I,J,KFORI0INPREKPREMFORI0IEMAXNFORI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1FORJI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1INTLIMIT_MAX_FLOWINTN,INTMATMAXN,INTBFMAXN,INTSOURCE,INTSINK,INTFLOWMAXNINTI,J,SK,KSIFSOURCESINKRETURNINFFORMATNN1MATN1NMATNNMATN1N1I0IEMAXNFORI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1FORJI0I0FLOWPREI1IDSINK,IPREI1ELSE29FLOWIPREI1DSINK,IPREI1INTLIMIT_MIN_FLOWINTN,INTMATMAXN,INTBFMAXN,INTSOURCE,INTSINK,INTFLOWMAXNINTI,J,SK,KSIFSOURCESINKRETURNINFFORMATNN1MATN1NMATNNMATN1N1I0I存放所有以I相鄰的點,包括反向邊DEFINEMAXN100DEFINEINF1000000000INTMAX_FLOWINTN,INTMATMAXN,VECTORLIST,INTSOURCE,INTSINK,INTFLOWMAXNINTPREMAXN,QUEMAXN,DMAXN,P,Q,T,I,J,RIFSOURCESINKRETURNINFFORI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1FORJI0IEMAXNIFSOURCESINKRETURNINFFORI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1FORJI0I0FLOWPREI1IDSINK,IPREI1ELSEFLOWIPREI1DSINK,IPREI1FORJI0ICJJIIFJCIELSEFLOWIPREI1DSINK,IPREI1FORJI0I03最短路徑單源DIJKSTRA_BFS正向表形式/單源最短路徑,用于路權相等的情況,DIJKSTRA優(yōu)化為BFS,正向表形式,復雜度OM/求出源S到所有點的最短路經(jīng),傳入圖的大小N和正向表LIST,BUF,邊權值LEN/返回到各點最短距離MIN和路徑PRE,PREI記錄S到I路徑上I的父結點,PRES1/可更改路權類型,但必須非負且相等DEFINEMAXN200DEFINEINF1000000000TYPEDEFINTELEM_TVOIDDIJKSTRAINTN,INTLIST,INTBUF,ELEM_TLEN,INTS,ELEM_TMIN,INTPREINTI,QUEMAXN,F0,R0,P1,L1,TFORI0I1HPHP1,P1HPEINTDELHEAP_TFOREHP1,C2CNEXTIFVTTO5最短路徑單源DIJKSTRABINARY_HEAP正向表形式/單源最短路徑,DIJKSTRA算法二分堆,正向表形式,復雜度OMLOGM/求出源S到所有點的最短路經(jīng),傳入圖的大小N和正向表LIST,BUF/返回到各點最短距離MIN和路徑PRE,PREI記錄S到I路徑上I的父結點,PRES1/可更改路權類型,但必須非負DEFINEMAXN200DEFINEINF1000000000TYPEDEFINTELEM_TSTRUCTEDGE_TINTTOELEM_TLENDEFINE_CPA,BAD1HPHP1,P1HPEINTDELHEAP_TFOREHP1,C2C1HMAPINDPINDP1PHP1,P1HMAPINDPIPEINTDELINTI,ELEM_TIFINRETURN0FOREHPIP1HMAPINDPINDP1PHP1,P1FORC2CNEXTIFVTTO7最短路徑單源DIJKSTRAMAPPED_HEAP正向表形式/單源最短路徑,DIJKSTRA算法映射二分堆,正向表形式,復雜度OMLOGN/求出源S到所有點的最短路經(jīng),傳入圖的大小N和正向表LIST,BUF/返回到各點最短距離MIN和路徑PRE,PREI記錄S到I路徑上I的父結點,PRES1/可更改路權類型,但必須非負DEFINEMAXN200DEFINEINF1000000000TYPEDEFINTELEM_TSTRUCTEDGE_TINTTOELEM_TLENDEFINE_CPA,BA1HMAPINDPINDP1PHP1,P1HMAPINDPIPEINTDELINTI,ELEM_TIFINRETURN0FOREHPIP1HMAPINDPINDP1PHP1,P1FORC2CDFNNOWKEYCNT0I,KEYCNT1NOWIFLOWIDFNNOWIFNOWROOTELSEIFNOWROOTRDELSEIFDFNI1RETURNRET423無向圖塊BFS鄰接陣形式/無向圖的塊,DFS鄰接陣形式,ON2/每產(chǎn)生一個塊調(diào)用DUMMY/傳入圖的大小N和鄰接陣MAT,不相鄰點邊權0DEFINEMAXN100INCLUDEVOIDDUMMYINTN,INTAFORINTI0IDFNNOWFORSTSP1,A0NOW,M1STSPIAMSTSPDUMMYM,AELSEIFDFNI0IWHILEMATNOWIMATNOWI,MATINOWFIND_PATH_UN,MAT,I,STEP,PATHPATHSTEPNOWVOIDFIND_PATH_DINTN,INTMATMAXN,INTNOW,INTFORIN1I0IWHILEMATNOWIMATNOWIFIND_PATH_DN,MAT,I,STEP,PATHPATHSTEPNOWINTEUCLID_PATHINTN,INTMATMAXN,INTSTART,INTPATHINTRET0FIND_PATH_UN,MAT,START,RET,PATH/FIND_PATH_DN,MAT,START,RET,PATHRETURNRET2前序表轉(zhuǎn)化/將用邊表示的樹轉(zhuǎn)化為前序表示的樹/傳入節(jié)點數(shù)N和鄰接表LIST,鄰接表必須是雙向的,會在函數(shù)中釋放/PRE返回前序表,MAP返回前序表中的節(jié)點到原來節(jié)點的映射DEFINEMAXN10000STRUCTNODEINTTONODENEXTVOIDPRENODEINTN,NODELIST,INTPRE,INTMAP,INTV,INTNOW,INTLAST,INTINTPIDFORVMAPPNOW1,PREPLASTLISTNOWTLISTNOW,LISTNOWTNEXTIFVTTOPRENODEN,LIST,PRE,MAP,V,TTO,P,ID47VOIDMAKEPREINTN,NODELIST,INTPRE,INTMAPINTVMAXN,ID0,IFORI0I0IIFCISETI1IFPREI1CPREI1RETRETURNRET/最大邊獨立集INTMAX_EDGE_INDEPENDENTINTN,INTPRE,INTSETINTCMAXN,I,RET0FORI0I0IIFCICPREI1RETRETURNRET/最小頂點覆蓋集INTMIN_NODE_COVERINTN,INTPRE,INTSETINTCMAXN,I,RET0FORI0I0IIFCI48CPREI1RETRETURNRET/最小頂點支配集INTMIN_NODE_DOMINANTINTN,INTPRE,INTSETINTCMAXN,I,RET0FORI0I0IIFCICPREI1IFPREPREI1CPREPREI1ELSESETI1RETRETURNRET4拓撲排序鄰接陣形式/拓撲排序,鄰接陣形式,復雜度ON2/如果無法完成排序,返回0,否則返回1,RET返回有序點列/傳入圖的大小N和鄰接陣MAT,不相鄰點邊權0DEFINEMAXN100INTTOPOSORTINTN,INTMATMAXN,INTRETINTDMAXN,I,J,KFORI0ICJJIIFJCIIFJCIIFJCIIFJCIFOR_CLRMATCH1,_CLRMATCH2,I0I0FOR_CLRT,SPQ0IP0JPMATCH2JKTJ,PMATCH1K,MATCH1KJRETURNRETINLINEINTPATH_COVERINTN,INTMATMAXN,INTPRE,INTNEXTRETURNNHUNGARYN,MAT,NEXT,PRE八圖論_NP搜索1最大團N小于64FASTER/WISHINGBONESACM/ICPCROUTINELIBRARYMAXIMUMCLIQUESOLVER/INCLUDEUSINGSTDVECTOR/CLIQUESOLVERCALCULATESBOTHSIZEANDCONSITUTIONOFMAXIMUMCLIQUE/USESBITOPERATIONTOACCELERATESEARCHING/GRAPHSIZELIMITIS63,THEGRAPHSHOULDBEUNDIRECTED/CANOPTIMIZETOCALCULATEONEACHCOMPONENT,ANDSORTONVERTEXDEGREES/CANBEUSEDTOSOLVEMAXIMUMINDEPENDENTSETCLASSCLIQUEPUBLICSTATICCONSTLONGLONGONE1STATICCONSTLONGLONGMASK11ICLIQUEDELETEBITS/SEARCHROUTINEBOOLSEARCHINTSTEP,INTSIZE,LONGLONGMORE,LONGLONGCON/SOLVEMAXIMUMCLIQUEANDRETURNSIZEINTSIZECLIQUEVECTOR/SOLVEMAXIMUMCLIQUEANDRETURNCONSTITUTIONVECTORCONSCLIQUEVECTOR/SEARCHROUTINE/STEPISNODEID,SIZEISCURRENTSOLUTION,MOREISAVAILABLEMASK,CONSISCONSTITUTIONMASKBOOLCLIQUESEARCHINTSTEP,INTSIZE,LONGLONGMORE,LONGLONGCONSIFSTEPN/ANEWSOLUTIONREACHEDTHISSIZESIZETHISCONSCONSRETURNTRUELONGLONGNOWONE0LONGLONGNEXTMOREIFSIZEBITSNEXTLONGLONGNEXTMOREIFSIZEBITSNEXT56RETURNFALSE/SOLVEMAXIMUMCLIQUEANDRETURNSIZEINTCLIQUESIZECLIQUEVECTOR/GENERATEMASKVECTORSFORINTI0I0MASKI|ONE0ISEARCHI1,1,MASKI,ONECLIQUECONSCLIQUEVECTORVECTORRETFORINTI0I0RETPUSH_BACKIRETURNRET2最大團/最大團/返回最大團大小和一個方案,傳入圖的大小N和鄰接陣MAT/MATIJ為布爾量DEFINEMAXN60VOIDCLIQUEINTN,INTU,INTMATMAXN,INTSIZE,INTIFNIFSIZECU0MAXMAXSIZEFORI0I0IFORVN0,JI1JVOIDDUMMYINTA,INTNINTICOUT0KNIFORJI1J0IPITNI,T/NIFORIN1IIFORJI1J0JIFPJKCOMBNJ,MI1TK,J6組合公式1CM,NCM,MN2CM,NCM1,NCM1,N1DERANGEMENTDNN11/11/21/31N/NN1DN2DN1QNDNDN1求和公式,K1N1SUMKNN1/22SUM2K1N23SUMK2NN12N1/64SUM2K12N4N21/35SUMK3NN1/226SUM2K13N22N217SUMK4NN12N13N23N1/308SUMK5N2N122N22N1/129SUMKK1NN1N2/310SUMKK1K2NN1N2N3/412SUMKK1K2K3NN1N2N3N4/5十數(shù)值計算1定積分計算ROMBERG/ROMBERG求定積分輸入積分區(qū)間A,B，被積函數(shù)FX,Y,Z輸出積分結果FX,Y,Z示例DOUBLEF0DOUBLEX,DOUBLEL,DOUBLETRETURNSQRT10LLTTCOSTXCOSTX/DOUBLEINTEGRALDOUBLEA,DOUBLEB,DOUBLEFDOUBLEX,DOUBLEY,DOUBLEZ,DOUBLEEPS,DOUBLEL,DOUBLETDOUBLEROMBERGDOUBLEA,DOUBLEB,DOUBLEFDOUBLEX,DOUBLEY,DOUBLEZ,DOUBLEEPS,DOUBLEL,DOUBLETDEFINEMAX_N100062INTI,J,TEMP2,MINDOUBLEH,R2MAX_N,TEMP4FORI0IMINRETURNR1I1H050TEMP22FORJ0J0IPPXCI1RETURNPINTNEWTONDOUBLEX0,DOUBLER,DOUBLEC,DOUBLECP,INTN,DOUBLEA,DOUBLEB,DOUBLEEPSINTMAX_ITERATION1000INTI1DOUBLEX1,X2,FP,EPS2EPS/100X1X0WHILEI10RETURN0X2X1X2/FPIFFABSX1X2BRETURN0RX2RETURN1X1X2IRETURN0DOUBLEPOLYNOMIAL_ROOTDOUBLEC,INTN,DOUBLEA,DOUBLEB,DOUBLEEPSDOUBLECPINTIDOUBLEROOTCPDOUBLECALLOCN,SIZEOFDOUBLEFORIN1I0ICPII1CI1IFABROOTAABBROOTIFNEWTONA,FREECPIFFABSROOT0IAIAICIAI1XICIXI1XN1CN1X0AN1XN2XN1/CN1A0AN1AN2BN1FORINTIN2I0IXIAIXN1十一幾何1多邊形INCLUDEINCLUDEDEFINEMAXN1000DEFINEOFFSET10000DEFINEEPS1E8DEFINEZEROXX0XXEPS1XEPSTBARYCENTERP0,PI,PI1RETXTXT2RETYTYT2T1T2IFFABST1EPSRETX/T1,RETY/T1RETURNRET2多邊形切割/多邊形切割/可用于半平面交DEFINEMAXN100DEFINEEPS1E8DEFINEZEROXX0XXEPS69POINTINTERSECTIONPOINTU1,POINTU2,POINTV1,POINTV2POINTRETU1DOUBLETU1XV1XV1YV2YU1YV1YV1XV2X/U1XU2XV1YV2YU1YU2YV1XV2XRETXU2XU1XTRETYU2YU1YTRETURNRET/將多邊形沿L1,L2確定的直線切割在SIDE側(cè)切割,保證L1,L2,SIDE不共線VOIDPOLYGON_CUTINTINTM0,IFORI0IDEFINEEPS1E8DEFINEZEROXX0XXEPSINTSAME_SIDEPOINTP1,POINTP2,POINTL1,POINTL2RETURNXMULTL1,P1,L2XMULTL1,P2,L2EPS/判兩點在線段異側(cè),點在線段上返回0INTOPPOSITE_SIDEPOINTP1,POINTP2,LINELRETURNXMULTLA,P1,LBXMULTLA,P2,LBL2XEPS/計算CROSSPRODUCTP1P0XP2P0DOUBLEXMULTPOINTP1,POINTP2,POINTP0RETURNP1XP0XP2YP0YP2XP0XP1YP0YDOUBLEXMULTDOUBLEX1,DOUBLEY1,DOUBLEX2,DOUBLEY2,DOUBLEX0,DOUBLEY0RETURNX1X0Y2Y0X2X0Y1Y0/計算三角形面積,輸入三頂點DOUBLEAREA_TRIANGLEPOINTP1,POINTP2,POINTP3RETURNFABSXMULTP1,P2,P3/2DOUBLEAREA_TRIANGLEDOUBLEX1,DOUBLEY1,DOUBLEX2,DOUBLEY2,DOUBLEX3,DOUBLEY3RETURNFABSXMULTX1,Y1,X2,Y2,X3,Y3/2/計算三角形面積,輸入三邊長DOUBLEAREA_TRIANGLEDOUBLEA,DOUBLEB,DOUBLECDOUBLESABC/2RETURNSQRTSSASBSC77/計算多邊形面積,頂點按順時針或逆時針給出DOUBLEAREA_POLYGONINTN,POINTPDOUBLES10,S20INTIFORI0ICONSTDOUBLEPIACOS1/計算圓心角LAT表示緯度,90PIPIDLNGPIPIIFDLNGPIDLNGPIPIDLNGLAT1PI/180,LAT2PI/180RETURNACOSCOSLAT1COSLAT2COSDLNGSINLAT1SINLAT2/計算距離,R為球半徑DOUBLELINE_DISTDOUBLER,DOUBLELNG1,DOUBLELAT1,DOUBLELNG2,DOUBLELAT2DOUBLEDLNGFABSLNG1LNG2PI/180WHILEDLNGPIPIDLNGPIPIIFDLNGPIDLNGPIPIDLNGLAT1PI/180,LAT2PI/180RETURNRSQRT22COSLAT1COSLAT2COSDLNGSINLAT1SINLAT2/計算球面距離,R為球半徑INLINEDOUBLESPHERE_DISTDOUBLER,DOUBLELNG1,DOUBLELAT1,DOUBLELNG2,DOUBLELAT2RETURNRANGLELNG1,LAT1,LNG2,LAT27三角形INCLUDESTRUCTPOINTDOUBLEX,YSTRUCTLINEPOINTA,B78DOUBLEDISTANCEPOINTP1,POINTP2RETURNSQRTP1XP2XP1XP2XP1YP2YP1YP2YPOINTINTERSECTIONLINEU,LINEVPOINTRETUADOUBLETUAXVAXVAYVBYUAYVAYVAXVBX/UAXUBXVAYVBYUAYUBYVAXVBXRETXUBXUAXTRETYUBYUAYTRETURNRET/外心POINTCIRCUMCENTERPOINTA,POINTB,POINTCLINEU,VUAXAXBX/2UAYAYBY/2UBXUAXAYBYUBYUAYAXBXVAXAXCX/2VAYAYCY/2VBXVAXAYCYVBYVAYAXCXRETURNINTERSECTIONU,V/內(nèi)心POINTINCENTERPOINTA,POINTB,POINTCLINEU,VDOUBLEM,NUAAMATAN2BYAY,BXAXNATAN2CYAY,CXAXUBXUAXCOSMN/2UBYUAYSINMN/2VABMATAN2AYBY,AXBXNATAN2CYBY,CXBXVBXVAXCOSMN/2VBYVAYSINMN/2RETURNINTERSECTIONU,V79/垂心POINTPERPENCENTERPOINTA,POINTB,POINTCLINEU,VUACUBXUAXAYBYUBYUAYAXBXVABVBXVAXAYCYVBYVAYAXCXRETURNINTERSECTIONU,V/重心/到三角形三頂點距離的平方和最小的點/三角形內(nèi)到三邊距離之積最大的點POINTBARYCENTERPOINTA,POINTB,POINTCLINEU,VUAXAXBX/2UAYAYBY/2UBCVAXAXCX/2VAYAYCY/2VBBRETURNINTERSECTIONU,V/費馬點/到三角形三頂點距離之和最小的點POINTFERMENTPOINTPOINTA,POINTB,POINTCPOINTU,VDOUBLESTEPFABSAXFABSAYFABSBXFABSBYFABSCXFABSCYINTI,J,KUXAXBXCX/3UYAYBYCY/3WHILESTEP1E10FORK0KDISTANCEV,ADISTANCEV,BDISTANCEV,CUV80RETURNU8三維幾何/三維幾何函數(shù)庫INCLUDEDEFINEEPS1E8DEFINEZEROXX0XXEPSINTDOT_INPLANE_EXPOINT3P,POINT3S1,POINT3S2,POINT3S3RETURNDOT_INPLANE_INP,S1,S2,S3/判兩點在線段同側(cè),點在線段上返回0,不共面無意義INTSAME_SIDEPOINT3P1,POINT3P2,LINE3LRETURNDMULTXMULTSUBTLA,LB,SUBTP1,LB,XMULTSUBTLA,LB,SUBTP2,LBEPSINTSAME_SIDEPOINT3P1,POINT3P2,POINT3L1,POINT3L2RETURNDMULTXMULTSUBTL1,L2,SUBTP1,L2,XMULTSUBTL1,L2,SUBTP2,L2EPS/判兩點在線段異側(cè),點在線段上返回0,不共面無意義INTOPPOSITE_SIDEPOINT3P1,POINT3P2,LINE3LRETURNDMULTXMULTSUBTLA,LB,SUBTP1,LB,XMULTSUBTLA,LB,SUBTP2,LBEPSINTSAME_SIDEPOINT3P1,POINT3P2,POINT3S1,POINT3S2,POINT3S3RETURNDMULTPVECS1,S2,S3,SUBTP1,S1DMULTPVECS1,S2,S3,SUBTP2,S1EPS/判兩點在平面異側(cè),點在平面上返回0INTOPPOSITE_SIDEPOINT3P1,POINT3P2,PLANE3SRETURNDMULTPVECS,SUBTP1,SADMULTPVECS,SUBTP2,SADEFINEEPS1E8DEFINEZEROXX0XX011RET011VOID_GRAHAMINTN,POINTP,INTFORP1P2P0,I1IEPS|ZEROP1YPIYP2X/N,P2Y/NPKP0,P0P1QSORTP1,N1,SIZEOFPOINT,GRAHAM_CPFORCH0P0,CH1P1,CH2P2,SI3I2VOID_GRAHAMINTN,POINTP,INTFORP1P2P0,I1IEPS|ZEROP1YPIYP2X/N,P2Y/NPKP0,P0P1QSORTP1,N1,SIZEOFPOINT,GRAHAM_CPFORCH0P0,CH1P1,CH2P2,SI3I2ELSEIFPOINTAXPOINTBXEPSRETURN1ELSERETURN0INT_WIPESAMEPOINTP,INTNINTI,KQSORTP,N,SIZEOFPOINT,WIPESAME_CPFORKI1I0XXSTRUCTPOINTINTX,YINTGCDINTA,INTBRETURNBGCDB,ABA/多邊形上的網(wǎng)格點個數(shù)INTGRID_ONEDGEINTN,POINTPINTI,RET0FORI0IDEFINEEPS1E8STRUCTPOINTDOUBLEX,YDOUBLEXMULTPOINTP1,POINTP2,POINTP0RETURNP1XP0XP2YP0YP2XP0XP1YP0YDOUBLEDISTANCEPOINTP1,POINTP2RETURNSQRTP1XP2XP1XP2XP1YP2YP1YP2YDOUBLEDISPTOLINEPOINTP,POINTL1,POINTL291RETURNFABSXMULTP,L1,L2/DISTANCEL1,L2POINTINTERSECTIONPOINTU1,POINTU2,POINTV1,POINTV2POINTRETU1DOUBLETU1XV1XV1YV2YU1YV1YV1XV2X/U1XU2XV1YV2YU1YU2YV1XV2XRETXU2XU1XTRETYU2YU1YTRETURNRET/判直線和圓相交,包括相切INTINTERSECT_LINE_CIRCLEPOINTC,DOUBLER,POINTL1,POINTL2RETURNDISPTOLINEC,L1,L2EPS|T2EPSTXL1YL2YTYL2XL1XRETURNXMULTL1,C,TXMULTL2,