《2022年ACM经典代码代码库[收 .pdf》由会员分享，可在线阅读，更多相关《2022年ACM经典代码代码库[收 .pdf（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、吉林大学ACM/ICPC代码库吉林大学计算机科学与技术学院2005 级2007-2008 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 48 页 - - - - - - - - - 吉林大学 ACM Group 1文档变更记录 修订日期修订内容修订版本修订人2007 创建1.0 jojer（sharang、 xwbsw 、 Liuctic ）2008.10 修订1.1 Fandywang 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -
2、- - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 48 页 - - - - - - - - - 吉林大学 ACM Group 1目录目录 . 1Graph 图论 . 3|DAG的深度优先搜索标记. 3|无向图找桥 . 3|无向图连通度 ( 割) . 3|最大团问题DP + DFS . 3|欧拉路径 O(E) . 3|DIJKSTRA数组实现 O（N2 ） . 3|DIJKSTRA O(E * LOG E) . 4|BELLMANFORD单源最短路O(VE) . 4|SPFA(SHORTEST PATH FASTER ALGORITHM) . 4|第 K
3、短路（ DIJKSTRA）. 5|第 K 短路（ A* ） . 5|PRIM求 MST. 6|次小生成树O(V2). 6|最小生成森林问题(K颗树)O(MLOGM). . 6|有向图最小树形图 . 6|MINIMAL STEINER TREE . 7|TARJAN强连通分量 . 7|弦图判断 . 7|弦图的PERFECT ELIMINATION点排列 . 7|稳定婚姻问题O(N2) . 8|拓扑排序 . 8|无向图连通分支 (DFS/BFS邻接阵 ) . 8|有向图强连通分支(DFS/BFS邻接阵 )O(N2) . 8|有向图最小点基 ( 邻接阵 )O(N2) . 9|FLOYD求最小环 .
4、9|2-SAT问题 . 9Network 网络流 . 11|二分图匹配（匈牙利算法DFS 实现） . 11|二分图匹配（匈牙利算法BFS 实现） . 11|二分图匹配（ HOPCROFTCARP的算法） . 11|二分图最佳匹配（KUHN MUNKRAS算法 O(M*M*N) ） 11|无向图最小割O(N3) . 12|有上下界的最小 ( 最大) 流 . 12|DINIC最大流 O(V2* E) . 12|HLPP 最大流 O(V3) . 13|最小费用流O(V *E * F) . 14|最小费用流O(V2* F) . 14|最佳边割集 . 15|最佳点割集 . 15|最小边割集 . 15|最
5、小点割集（点连通度） . 16|最小路径覆盖O(N3) . 16|最小点集覆盖 . 16Structure 数据结构 . 17|求某天是星期几 . 17|左偏树 合并复杂度O(LOG N) . 17|树状数组 . 17|二维树状数组 . 17|TRIE树(K叉) . 18|TRIE树( 左儿子又兄弟 ) . 18|后缀数组O(N * LOG N) . 18|后缀数组O(N) . 18|RMQ离线算法O(N*LOGN)+O(1) . 19|RMQ(RANGE MINIMUM/MAXIMUM QUERY)-ST算法(O(NLOGN + Q) . 19|RMQ离线算法O(N*LOGN)+O(1)求解
6、 LCA. 19|LCA 离线算法O(E)+O(1). 20|带权值的并查集 . 20|快速排序 . 20|2 台机器工作调度. 20|比较高效的大数 . 20|普通的大数运算 . 21|最长公共递增子序列O(N2) . 22|0-1分数规划 . 22|最长有序子序列（递增/ 递减 / 非递增 / 非递减） . 22|最长公共子序列 . 23|最少找硬币问题（贪心策略- 深搜实现） . 23|棋盘分割 . 23|汉诺塔 . 24|STL 中的PRIORITY_QUEUE . 24|堆栈 . 24|区间最大频率 . 24|取第K个元素 . 25|归并排序求逆序数 . 25|逆序数推排列数 . 2
7、5|二分查找 . 25|二分查找（大于等于V的第一个值） . 26|所有数位相加 . 26名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 48 页 - - - - - - - - - 吉林大学 ACM Group 2Number 数论 . 27| 递推求欧拉函数PHI(I) . 27| 单独求欧拉函数PHI(X) . 27|GCD 最大公约数 . 27|快速 GCD . 27|扩展 GCD . 27|模线性方程 A * X = B (% N) . 27|模线性方程组 .
8、27|筛素数 1.N . 27|高效求小范围素数1.N . 27|随机素数测试 ( 伪素数原理 ) . 27|组合数学相关 . 27|POLYA计数 . 28|组合数 C(N, R) . 28|最大 1 矩阵 . 28|约瑟夫环问题（数学方法） . 28|约瑟夫环问题（数组模拟） . 28|取石子游戏1. 28|集合划分问题 . 28|大数平方根（字符串数组表示） . 29|大数取模的二进制方法 . 29|线性方程组AX=B. 29|追赶法解周期性方程 . 30|阶乘最后非零位 , 复杂度 O(NLOGN) . 30递归方法求解排列组合问题 . 31|类循环排列 . 31|全排列 . 31|不
9、重复排列 . 31|全组合 . 32|不重复组合 . 32|应用 . 33模式串匹配问题总结 . 33|字符串 HASH . 33|KMP匹配算法 O(M+N) . 33|KARP-RABIN字符串匹配 . 33|基于 KARP-RABIN的字符块匹配 . 33|函数名 : STRSTR . 34|BM算法的改进的算法SUNDAY ALGORITHM . 34|最短公共祖先（两个长字符串） . 34|最短公共祖先（多个短字符串） . 34Geometry 计算几何 . 35|GRAHAM求凸包O(N * LOGN) . 35|判断线段相交 . 35|求多边形重心 . 35|三角形几个重要的点
10、. 35|平面最近点对O(N * LOGN) . 35|LIUCTIC的计算几何库 . 36|求平面上两点之间的距离 . 36|(P1-P0)*(P2-P0)的叉积 . 36|确定两条线段是否相交 . 36|判断点P是否在线段L上. 36|判断两个点是否相等 . 36|线段相交判断函数 . 36|判断点Q是否在多边形内. 37|计算多边形的面积 . 37|解二次方程AX2+BX+C=0 . 37|计算直线的一般式AX+BY+C=0 . 37|点到直线距离 . 37|直线与圆的交点，已知直线与圆相交 . 37|点是否在射线的正向 . 37|射线与圆的第一个交点 . 37|求点P1 关于直线LN的
11、对称点P2. 37|两直线夹角（弧度） . 37ACM/ICPC 竞赛之 STL . 38ACM/ICPC 竞赛之 STL 简介 . 38ACM/ICPC 竞赛之 STL-PAIR . 38ACM/ICPC 竞赛之 STL-VECTOR . 39ACM/ICPC 竞赛之 STL-ITERATOR简介 . 39ACM/ICPC 竞赛之 STL-STRING . 40ACM/ICPC 竞赛之 STL-STACK/QUEUE . 40ACM/ICPC 竞赛之 STL-MAP . 41ACM/ICPC 竞赛之 STL-ALGORITHM. 42STL IN ACM . 43头文件 . 44线段树 .
12、44求矩形并的面积（线段树+离散化 +扫描线） . 44求矩形并的周长（线段树+离散化 +扫描线） . 45名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 48 页 - - - - - - - - - 吉林大学 ACM Group 3Graph 图论 | DAG的深度优先搜索标记 | INIT: edge邻接矩阵; pre, post, tag全置 0; | CALL: dfstag(i, n); pre/post:开始 / 结束时间*=*/int edgeVV, pre
13、V, postV, tag; void dfstag(int cur, int n) / vertex: 0 n-1precur = +tag; for (int i=0; i precur) printf(Down Edge!n); else printf(Cross Edge!n); postcur = +tag; | 无向图找桥 | INIT: edge邻接矩阵;vis,pre,anc,bridge 置 0; | CALL: dfs(0, -1, 1, n);*=*/int bridge, edgeVV, ancV, preV, visV; void dfs(int cur, int f
14、ather, int dep, int n) / vertex: 0 n-1if (bridge) return; viscur = 1; precur = anccur = dep; for (int i=0; in; +i) if (edgecuri) if (i != father & 1 = visi) if (prei anccur) anccur = prei;/back edge if (0 = visi) /tree edge dfs(i, cur, dep+1, n); if (bridge) return; if (anci precur) bridge = 1; retu
15、rn; viscur = 2; | 无向图连通度( 割) | INIT: edge邻接矩阵;vis,pre,anc,deg置为 0; | CALL: dfs(0, -1, 1, n); | k=deg0, degi+1(i=1n-1)为删除该节点后得到的连通图个数 | 注意 :0 作为根比较特殊! *=*/int edgeVV, ancV, preV, visV, degV; void dfs(int cur, int father, int dep, int n) / vertex: 0 n-1int cnt = 0; viscur = 1; precur = anccur = dep; f
16、or (int i=0; in; +i) if (edgecuri) if (i != father & 1 = visi) if (prei anccur) anccur = prei;/back edge if (0 = visi) /tree edge dfs(i, cur, dep+1, n); +cnt; / 分支个数if (anci 1) | (cnt!=0 & anci=precur) +degcur; / link degree of a vertex viscur = 2; | 最大团问题 DP + DFS | INIT: g邻接矩阵 ; | CALL: res = cliq
17、ue(n);*=*/int gVV, dpV, stkVV, mx; int dfs(int n, int ns, int dep) if (0 = ns) if (dep mx) mx = dep; return 1; int i, j, k, p, cnt; for (i = 0; i ns; i+) k = stkdepi; cnt = 0; if (dep + n - k = mx) return 0; if (dep + dpk = mx) return 0; for (j = i + 1; j = 0; i-) / vertex: 0 n-1for (ns = 0, j = i +
18、 1; j 0; v = w) stk top+ = v; w = adjv -cntv ; adjw idxwv = adjw -cntw ; / 处理的是无向图-边是双向的，删除v-w 后，还要处理删除w-v return v; void elpath (int b, int n) / begin from bint i, j; for (i = 0; i n; +i) / vertex: 0 n-1for (j = 0; j cnti; +j) idxi adjij = j; printf(%d , b); for (top = 0; path(b) = b & top != 0; )
19、b = stk -top ; printf(-%d, b); printf(n); | Dijkstra数组实现O（N2 ）| Dijkstra - 数组实现( 在此基础上可直接改为STL 的Queue 实现 ) | lowcost - beg到其他点的最近距离| path - beg为根展开的树，记录父亲结点*=*/ #define INF 0 x03F3F3F3F const int N; int pathN, visN; void Dijkstra(int costN, int lowcostN, int n, int beg) int i, j, min; memset(vis, 0,
20、 sizeof(vis); visbeg = 1; for (i=0; in; i+) lowcosti = costbegi; pathi = beg; lowcostbeg = 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 48 页 - - - - - - - - - 吉林大学 ACM Group 4pathbeg = -1; / 树根的标记int pre = beg; for (i=1; in; i+) min = INF; for (j=0; jn; j+
21、) / 下面的加法可能导致溢出,INF不能取太大 if (visj= =0 & lowcostpre+costprejlowcostj) lowcostj =lowcostpre + costprej; pathj =pre; for (j=0; jn; j+) if (visj = 0 & lowcostj min) min = lowcostj; pre = j; vispre = 1; | Dijkstra O(E * log E) | INIT: 调用 init(nv, ne)读入边并初始化; | CALL: dijkstra(n, src); disti为src 到i 的最短距离*=
22、*/#define typec int/ type of costconst typec inf = 0 x3f3f3f3f; / max of costtypec costE, distV; int e, pntE, nxtE, headV, prevV, visV; struct qnode int v; typec c; qnode ( int vv = 0, typec cc = 0) : v(vv), c(cc) booloperator r.c; ; void dijkstra(int n, constint src) qnode mv; int i, j, k, pre; pri
23、ority_queue que; vissrc = 1; distsrc = 0; que.push(qnode(src, 0); for (pre = src, i=1; in; i+) for (j = headpre; j != -1; j = nxtj) k =pntj; if (visk = 0 & distpre + costj distk) distk =distpre + costj; que.push(qnode(pntj, distk); prevk =pre; while (!que.empty() & visque.top().v = 1) que.pop(); if
24、(que.empty() break; mv = que.top(); que.pop(); vispre = mv.v = 1; inlinevoid addedge(int u, int v, typec c) pnte = v; coste = c; nxte = headu; headu = e+; void init(int nv, int ne) int i, u, v; typec c; e = 0; memset(head, -1, sizeof(head); memset(vis, 0, sizeof(vis); memset(prev, -1, sizeof(prev);
25、for (i = 0; i nv; i+) disti = inf; for (i = 0; i =表示求最小值 , 作为最长路，=表示求最大值, 作为最短路（v-u distu + c) distv = distu + c; prev =u; return 1; return 0; int bellman (int src) int i, j; for (i=0; in; +i) disti = inf; prei = -1; distsrc = 0; bool flag; for (i=1; in; +i) flag = false; / 优化for (j=0; jm; +j) if( 1
26、 = relax(edgej0, edgej1, edgej2) ) flag = true; if( !flag ) break; for (j=0; jm; +j) if(1 = relax(edgej0, edgej1, edgej2) return 0; / 有负圈 return 1; | SPFA(Shortest Path Faster Algorithm) Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。原理：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估
27、计值的改变。判断负权回路：记录每个结点进队次数，超过|V|次表示有负权。*=*/ / POJ 3159 Candies const int INF = 0 x3F3F3F3F; const int V = 30001; const int E = 150001; int pntE, costE, nxtE; int e, headV; int distV; bool visV; int main(void) int n, m; while( scanf(%d%d, &n, &m) != EOF ) int i, a, b, c; e =0; memset(head, -1, sizeof(he
28、ad); for( i=0; i m; +i ) / b-a distu + c ) distv = distu + c; return 1; return 0; inline void addedge(int u, int v, int c) pnte = v; coste = c; nxte = headu; headu = e+; int SPFA(int src, int n) / 此处用堆栈实现，有些时候比队列要快int i; for( i=1; i = n; +i ) / 顶点 1.n visi = 0; disti = INF; distsrc = 0; int QE, top
29、= 1; Q0 = src; vissrc = true; while( top ) int u, v; u = Q-top; visu = false; for( i=headu; i != -1; i=nxti ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 48 页 - - - - - - - - - 吉林大学 ACM Group 5 v =pnti; if( 1 = relax(u, v, costi) & !visv ) Qtop+ = v; visv =
30、true; return distn; / 队列实现，而且有负权回路判断POJ 3169 Layout #define swap(t, a, b) (t=a, a=b, b=t) const int INF = 0 x3F3F3F3F; const int V = 1001; const int E = 20001; int pntE, costE, nxtE; int e, headV, distV; bool visV; int cntV; / 入队列次数int main(void) int n, ml, md; while( scanf(%d%d%d, &n, &ml, &md) !=
31、EOF ) int i, a, b, c, t; e =0; memset(head, -1, sizeof(head); for( i=0; i ml; +i ) / 边方向！ / 大- 小 b) swap(t, a, b); addedge(a, b, c); for( i=0; i =c = 小- 大=-c, 有向边 ( 大, 小):-c scanf(%d%d%d, &a, &b, &c); if( a b ) swap(t, a, b); addedge(a, b, -c); /for( i=1; i distu + c ) distv = distu + c; return 1; r
32、eturn 0; inline void addedge(int u, int v, int c) pnte = v; coste = c; nxte = headu; headu = e+; int SPFA(int src, int n)/ 此处用队列实现int i; memset(cnt, 0, sizeof(cnt); / 入队次数memset(vis, false, sizeof(vis); for( i=1; i = n; +i ) disti = INF; distsrc = 0; queue Q; Q.push(src); vissrc = true; +cntsrc; whi
33、le( !Q.empty() ) int u, v; u = Q.front(); Q.pop(); visu = false; for( i=headu; i != -1; i=nxti ) v =pnti; if( 1 = relax(u, v, costi) & !visv ) Q.push(v); visv =true; if( (+cntv) n ) return -1; / cnti为入队列次数，用来判断是否存在负权回路 if( distn = INF ) return -2; / src与n不可达，有些题目可省！return distn; / 返回 src到n的最短距离，根据题意
34、不同而改变 | 第 K 短路（ Dijkstra） | dij变形，可以证明每个点经过的次数为小于等于K， 所有把 dij的数组 dist | 由一维变成2维，记录经过该点1次， 2 次。 k 次的最小值。 | 输出 distn-1k即可*=*/WHU1603 int g10101010; int n,m,x; const int INF=1000000000; int v1010; int dist101020; int main() while (scanf(%d%d%d,&n,&m,&x)!=EOF) for (int i=1;i=n;i+) for (int j=1;j=n;j+) g
35、ij=INF; for (int i=0;im;i+) int p,q,r; scanf(%d%d%d,&p,&q,&r); if (rgpq) gpq=r; for (int i=1;i=n;i+) vi=0; for (int j=0;j=x;j+) distij=INF; dist10=0; dist00=INF; while (1) int k=0; for (int i=1;i=n;i+) if (vix & distividistk0) k=i; if (k=0) break; if (k=n & vn=x-1) break; for (int i=1;i=n;i+) if (vi
36、x & distkvk+gki0;j-) if (distijdistij-1) swap(distij,distij-1); vk+; if (distnx-1INF) printf(%dn,distnx-1); else printf(-1n); return 0; | 第 K 短路（ A* ） | A* 估价函数 fi为到当前点走过的路经长度， hi为该点到终点的长度 | gi=hi+fi；*=*/WHU1603 int n,m,x,ct; int g10101010,gr10101010; int dist1010,v1010; const int INF=1000000000; st
37、ruct node int id,fi,gi; friend bool operator b.fi; return a.gib.gi; s2000010; int init() for (int i=0;i=n;i+) disti=INF; vi=1; distn-1=0; for (int i=0;in;i+) int k=n; for (int j=0;jn;j+) if (vj & distjdistk) k=j; if (k= =n) break; vk=0; for (int j=0;jn;j+) if (vj & distk+grkjdistj) distj=distk+grkj;
38、 return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 48 页 - - - - - - - - - 吉林大学 ACM Group 6int solve() if (dist0=INF) return -1; ct=0; sct.id=0; sct.fi=0; sct+.gi=dist0; int cnt=0; while (ct) int id=s0.id,fi=s0.fi,gi=s0.gi; if (id=n-1) cnt+; if (cnt=x) re
39、turn fi; pop_heap(s,s+ct); ct-; for (int j=0;jn;j+) if (gidjINF) sct.id=j; sct.fi=fi+gidj; sct+.gi=sct.fi+distj; push_heap(s,s+ct); return -1; int main() while (scanf(%d%d%d,&n,&m,&x)!=EOF) for (int i=0;in;i+) for (int j=0;jn;j+) grij=gij=INF; for (int i=0;im;i+) int x,y,z; scanf(%d%d%d,&x,&y,&z); x
40、-,y-; gxy?=z; gryx?=z; init(); printf(%dn,solve(); return 0; | Prim求 MST | INIT: cost耗费矩阵(inf为无穷大 ); | CALL: prim(cost, n); 返回 -1 代表原图不连通;*=*/#define typec int/ type of costconst typec inf = 0 x3f3f3f3f; / max of costint visV; typec lowcV; typec prim(typec costV, int n) / vertex: 0 n-1 int i, j, p;
41、typec minc, res = 0; memset(vis, 0, sizeof(vis); vis0 = 1; for (i=1; in; i+) lowci = cost0i; for (i=1; in; i+) minc = inf; p = -1; for (j=0; j lowcj) minc = lowcj; p = j; if (inf = minc) return -1; / 原图不连通 res += minc; visp = 1; for (j=0; j costpj) lowcj =costpj; return res; | 次小生成树O(V2) *=*/结论次小生成树
42、可由最小生成树换一条边得到. 证明 : 可以证明下面一个强一些的结论： T是某一棵最小生成树，T0 是任一棵异于T的树， 通过变换T0 - T1 - T2 - . - Tn (T) 变成最小生成树. 所谓的变换是，每次把T_i 中的某条边换成T 中的一条边, 而且树 T_(i+1)的权小于等于T_i 的权 . 具体操作是： step 1. 在T_i 中任取一条不在T中的边 u_v. step 2. 把边 u_v 去掉，就剩下两个连通分量A和B，在 T中，必有唯一的边u_v 连结 A和B. step 3. 显然 u_v的权比 u_v 小 ( 否则 ,u_v就应该在 T中). 把u_v替换 u_v
43、 即得树 T_(i+1). 特别地：取Tn 为任一棵次小生成树，T_(n-1) 也就是次小生成树且跟T差一条边 . 结论得证 . 算法：只要充分利用以上结论, 即得 V2 的算法 . 具体如下：step 1. 先用 prim求出最小生成树T. 在prim的同时，用一个矩阵maxuv 记录在 T中连结任意两点u,v的唯一的路中权值最大的那条边的权值 . ( 注意这里 ). 这是很容易做到的，因为 prim 是每次增加一个结点s, 而设已经标号了的结点集合为W, 则W 中所有的结点到s的路中的最大权值的边就是当前加入的这条边. step 1 用时 O(V2). step 2. 枚举所有不在T中的边
44、 u_v, 加入边 u_v 替换权为 maxuv的边 . 不断更新求最小值，即次小生成树. step 2 用时 O(E).故总时间为O(V2). | 最小生成森林问题(k颗树 )O(mlogm). *=*/数据结构：并查集算法：改进Kruskal 根据 Kruskal算法思想，图中的生成树在连完第n-1 条边前，都是一个最小生成森林，每次贪心的选择两个不属于同一连通分量的树（如果连接一个连通分量，因为不会减少块数，那么就是不合算的）且用最“便宜”的边连起来，连接n-1 次后就形成了一棵MST，n-2 次就形成了一个两棵树的最小生成森林，n-3 ， n-k 此后就形成了k颗树的最小生成森林，就是
45、题目要求求解的。 | 有向图最小树形图 | INIT: eg置为边表 ; res置为 0; cpi置为 i; | CALL: dirtree(root, nv, ne); res是结果 ;*=*/#define typec int/ type of resconst typec inf = 0 x3f3f3f3f; / max of restypec res, disV; int toV, cpV, tagV; struct Edge int u, v; typec c; egE; int iroot(int i) if (cpi = i) return i; return cpi = iro
46、ot(cpi); int dirtree(int root, int nv, int ne) / root: 树根 / vertex: 0 n-1int i, j, k, circle = 0; memset(tag, -1, sizeof(tag); memset(to, -1, sizeof(to); for (i = 0; i nv; +i) disi = inf; for (j = 0; j egj.c) disk =egj.c; tok =i; toroot = -1; disroot = 0; tagroot = root; for (i = 0; i nv; +i) if (cp
47、i = i & -1 = tagi) j =i; for ( ; j != -1 & tagj = -1; j = toj) tagj = i; if (j = -1) return 0; if (tagj = i) circle = 1; tagj = -2; for (k = toj; k != j; k = tok) tagk = -2; if (circle) for (j = 0; j ne; +j) i = iroot(egj.u); k = iroot(egj.v); if (k != i & tagk = -2) egj.c -= disk; for (i = 0; i nv;
48、 +i) if (tagi = -2) res += disi; tagi = 0; for (j = toi; j != i; j = toj) res += disj; cpj = i; tagj = 0; if (0 = dirtree(root, nv, ne) return 0; else for(i = 0; i nv; +i) if(cpi = i) res += disi; return 1; / 若返回 0代表原图不连通 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
49、第 8 页，共 48 页 - - - - - - - - - 吉林大学 ACM Group 7 | Minimal Steiner Tree | G(V, E), A是 V的一个子集, 求至少包含A中所有点的最小子树. | 时间复杂度: O(N3 + N * 2A * (2A + N) | INIT: d距离矩阵 ; id置为集合 A中点的标号; | CALL: steiner(int n, int a); | main()函数解决的题目: Ticket to Ride, NWERC 2006/2007 | 给4个点对 (a1, b1) . (a4, b4), | 求min(sigma(dis
50、taibi),其中重复的路段只能算一次. | 这题要找出一个steiner森林 , 最后要对森林中树的个数进行枚举*=*/#define typec int/ type of costconst typec inf = 0 x3f3f3f3f; / max of costint visV, idA; /id: A中点的标号typec dVV, dp1AV;/dpiv: 点v到点集 i 的最短距离void steiner(int n, int a) int i, j, k, mx, mk, top = (1 a); for (k = 0; k n; k+) for (i = 0; i n; i+