ACM程序集_wangLuoYan.doc

目录 一、最短路 1 二、凸包 5 三、增广路网络流 7 四、最高标号预流推进法 11 五、最小费用最大流 15 六、博弈 19 七、字符串 20 八、高精度 35 一、最短路 #include iostream using namespace std; typedef long long WeightType; //Notice here, to make sure that its wast exceed const WeightType InfiniteWeight=(WeightType)2147483647*2147483647; struct Edge{ int v; WeightType w; Edge *next; }; class Graph{ int n; int heapSize; int *heap,*sort; WeightType *w; Edge **G; public: Graph(){n=0;} ~Graph(){ClearGraph();} void ClearGraph(); void SetGraphSize(int size); int GetGraphSize(){return n;} void InsertEdge(int u,int v,WeightType w); void HeapAssign(int i,int v){heap[i]=v; sort[v]=i;} void HeapSift(int i,int m); void HeapUpdate(int i); void HeapDelete(int i) { sort[heap[i]]=-1; --heapSize; if (heapSize==0) return; HeapAssign(i,heap[heapSize+1]); HeapUpdate(i); } //-1 means vertex heap[i] has been extended. void HeapInsert(int v) { ++heapSize; HeapAssign(heapSize,v); HeapUpdate(heapSize);} WeightType* HeapOptimizedDijkstra(int s); void Print(); }; void Graph::InsertEdge(int u,int v,WeightType w){ static Edge *p; p=new Edge; p-v=v; p-w=w; p-next=G[u]; G[u]=p; } void Graph::SetGraphSize(int size){ ClearGraph(); n=size; G=new Edge*[size]; memset(G,NULL,sizeof(Edge*)*size); heap=new int[size+1]; //this is very important. sort=new int[size]; } void Graph::ClearGraph(){ if (n==0) return; static int i; static Edge *p; for (i=0; in; i++) { while (G[i]) { p=G[i]; G[i]=G[i]-next; delete p; } } delete []G; delete []heap; delete []sort; n=0; } void Graph::Print(){ static Edge *p; static int i; i=0; for (i=0; in; i++) { p=G[i]; while (p) { couti p-v weight=p-wendl; p=p-next; } if (G[i]) coutendl; } } void Graph::HeapSift(int i,int m){ static int v,j; v=heap[i]; j=i1; while (j=m) { if (jmw[heap[j+1]]w[heap[j]]) ++j; if (w[heap[j]]w[v]) { HeapAssign(i,heap[j]); i=j; j=1; } else break; } HeapAssign(i,v); } void Graph::HeapUpdate(int i){ static int v; v=he