对参加ACM竞赛非常有用的几个ACM答题模板（数论

				//无向图最小生成树,prim算法+二分堆,邻接表形式,复杂度O(mlogm)
				//返回最小生成树的长度,传入图的大小n和邻接表list
				//可更改边权的类型,pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1
				//必须保证图的连通的!
				#define MAXN 200
				#define inf 1000000000
				typedef double elem_t;
				struct edge_t{
					int from,to;
					elem_t len;
					edge_t* next;
				};
				
				#define _cp(a,b) ((a).d				struct heap_t{elem_t d;int v;};
				struct heap{
					heap_t h[MAXN*MAXN];
					int n,p,c;
					void init(){n=0;}
					void ins(heap_t e){
						for (p=++n;p>1&&_cp(e,h[p>>1]);h[p]=h[p>>1],p>>=1);
						h[p]=e;
					}
					int del(heap_t& e){
						if (!n) return 0;
						for (e=h[p=1],c=2;c						h[p]=h[n--];return 1;
					}
				};
				
				elem_t prim(int n,edge_t* list[],int* pre){
					heap h;
					elem_t min[MAXN],ret=0;
					edge_t* t;heap_t e;
					int v[MAXN],i;
					for (i=0;i						min[i]=inf,v[i]=0,pre[i]=-1;
					h.init();e.v=0,e.d=0,h.ins(e);
					while (h.del(e))
						if (!v[e.v])
							for (v[e.v]=1,ret+=e.d,t=list[e.v];t;t=t->next)
								if (!v[t->to]&&t->lento])
									pre[t->to]=t->from,min[e.v=t->to]=e.d=t->len,h.ins(e);
					return ret;
				}