《ACM+算法集--常用ACM算法》由会员分享，可在线阅读，更多相关《ACM+算法集--常用ACM算法（20页珍藏版）》请在金锄头文库上搜索。
1、图算法kurXX 最小生成树#include #include #include using namespace std;#define M 501#define LIM 20000000struct edgint u,v;int w;all_eM*M/2;bool operator t;for(k=0;k n;int ei=0;for(i=1;iall_emax.w) max=i;printf(%dn,all_emax.w);return 0;Prim#include using namespace std;#define M 2001int setM=0,gMM;char strM8;in
2、line void make_map(int n,int gMM)int i,j,k;for(i=1;i#include #include #include ;using namespace std;#define M 1001#define LIM 2000000000struct dd /最短距离int w,q;/w 是距离值,q 是堆中的相对位置dM,d2M;struct nodeint v,w;int hM,hs;vector gM,g2M;void change_key(dd dM,int v,int w)dv.w=w;int i=dv.q;while(i1 & dhi/2.wdhi
3、.w)swap(hi,hi/2);swap(dhi.q,dhi/2.q);i=i/2;inline void min_heaphy(dd dM,int *a,int i,int s)/s 为堆大小int l=i*2,r=i*2+1;int miner=i;if (ldal.w)miner = l;else miner=i;if (rdar.w)miner=r;if(miner!=i)swap(ai,aminer);swap(dai.q,daminer.q);min_heaphy(d,a,miner,s);inline void init(dd dM,int n,int s) /初始化图和堆in
4、t i;hs=n;for(i=1;idu.w+duv) change_key(d,v,du.w+duv);void dijkstra(vector gM,dd dM,int n,int s) /n is |V| & s is the sourceinit(d,n,s);int i;while(hs!=0)int u=h1;swap(h1,hhs);swap(dh1.q,dhhs.q);hs-;min_heaphy(d,h,1,hs);for(i=0;idu+duv) dv=du+duv;void dijkstra(int gMM,int dM,int n,int s) /n is |V| &
5、s is the sourceinit(d,n,s);int qM,ql=1,qf=1; /队列int i;for(i=1;i#include using namespace std;#define M 301#define LIM 200000000int wMM,d2MM;void floyd(int gMM,int d2MM,int n)int i,j,k;for(i=1;idu+duv) dv=du+duv;void bell_man(int gMM,int dM,int n,int s) /n 个结点 s 为源点int i,j,k;init(d,n,s);for(k=1;k#incl
6、ude #include #include using namespace std;vector order;void find_id(list g,int id,int n) /寻找入度,没有使用int i;list:iterator k;for(i=0;i g,int id,int n,bool &OK,bool &incon)/OK=false 表示未确定顺序 incon=true 表示发现矛盾stack s;order.erase(order.begin(),order.end();int t26;copy(&id0,&idn,&t0);int i;for(i=0;i:iterator
7、 k;for(k=gv.begin();k!=gv.end();k+)id*k-;if(id*k=0) s.push(*k);if(s.size()1) OK=false;if(order.size() #include #include using namespace std;#define M 20005vector gM,gtM;bool usedM;int ftM,sort_vM,tim;bool comp(const int &u,const int &v)return ftuftv;inline int findp(int set,int n)int n2=n;while(setn
8、!=0) n=setn;if(n2!=n) setn2=n;return n;inline bool uni(int set,int a,int b) int ac=0,a2=a,b2=b,bc=0,t;while(seta!=0) a=seta;ac+;while(a2!=a) t=seta2; seta2=a; a2=t;while(setb!=0) b=setb;bc+;while(b2!=b) t=setb2; setb2=b; b2=t; if(a=b) return false;if(ac gM,int u)if(usedu) return;tim+;usedu=true;int
9、i;for(i=0;i g,int u,int r,int set)if(usedu) return;uni(set,u,r);usedu=true;int i;for(i=0;i gM,int set)int i,j;tim=0;memset(used,0,sizeof(used);memset(set,0,sizeof(set);for(i=1;i n m;for(i=0;i#include #include using namespace std;#define M 1001int n,m,matchM,ansM;bool visitM,gMM;/O(n3)bool dfs(int k,
10、bool mapMM) int t;for(int i = 1; i t;while(t-)sum=0;memset(match,0,sizeof(match);memset(g,0,sizeof(g);scanf(%d%d,&n,&m);for(i=1;i#include #include #include using namespace std;#define M 3001bool gMM;int mkM ,cxM,predM,openM,cyM,nx,ny;/边少适用 O(n3)int MaxMatchBFS()int i , u , v , t , d , e , cur , tail
11、 , res(0) ;memset(mk , 0xff , sizeof(mk) ; memset(cx , 0xff , sizeof(cx) ;memset(cy , 0xff , sizeof(cy) ;for (i = 0 ; i = 0) predopentail = u ; continue ; for (d = u , e = v ; d != -1 ; t = cxd , cxd = e , cye = d , e = t , d = predd) ;if (cxi != -1) res+ ;return res ;int path(int u)for (int v = 0 ;
12、 v #include #include using namespace std;#define M 110int n; / X 的大小int lxM, lyM; / 标号bool sxM, syM; / 是否被搜索过int matchM; / Y(i) 与 X(match i) 匹配/ 从 X(u) 寻找增广道路，找到则返回 truebool path(int u,int weightMM) sx u = true;for (int v = 0; v n m & (n!=0 | m!=0)vector vh,vm;for(i=0;i g,vector &vans) /O（E2）int j,w
13、,v,t;for(j=gu.size()-1;j=0;j-)t=v=guj; w=u;if(vw) swap(v,w);if(usedvw!=0)usedvw-;dfs(t,g,vans);vans.push_back(u);有向图：int n,m;vector gM,vans;void dfs(int u) /O（E2*log(e)）int j,t;Edg et;for(j=gu.size()-1;j=0;j-)et.u=u; et.v=guj;if(mpet!=0)mpet-;dfs(guj);vans.push_back(u);【最大流】Edmonds Karp/求最小割集合的办法:/设
14、置一个集合 A, 最开始 A=s,按如下方法不断扩张 A:/1 若存在一条边(u,v), 其流量小于容量，且 u 属于 A,则 v 加入 A/2 若存在(v,u), 其流量大于 0，且 u 属于 A,则 v 加入 A/A 计算完毕，设 B=V-A，/最大流对应的割集 E=(u,v) | uA,vB/E 为割集，这是一定的/【最大流】Edmonds Karp 算法求最大流,复杂度 O(V E2)。返回最大流,输入图容量/矩阵 gMM,取非零值表示有边，s 为源点，t 为汇点，fMM返回流量矩阵。int fMM,gMM;int EdmondsKarp(int n,int s,int t)int i,j,k,c,head,tail,flow=0;int rMM;int prevM,visitM,qM;for (i=1;i0) visiti=1;previ=k;if (i=t) goto next;qtail+=i;next:if (!visitt) break; /流量已达到最大c=99999999;j=t;while (j!=s) i=prevj;if
