《ACM算法集锦》由会员分享，可在线阅读，更多相关《ACM算法集锦（23页珍藏版）》请在金锄头文库上搜索。
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 (const edg &a,const edg &b)return a.wb.w;int setM;inline bool uni(int set,int a,int b) int ac=0,a2=a,b2=b,bc=0;while(seta!=0) a=seta;ac+;if(a2!=a) seta2=a;while(
2、setb!=0) b=setb;bc+;if(b2!=b) setb2=b; if(a=b) return false;if(ac t;for(k=0;k n;int ei=0;for(i=1;i=n;i+)for(j=1;j=n;j+)if(t!=0)edg e;e.u=i;e.v=j;scanf(%d,&e.w);if(ij)all_eei+=e;sort(&all_e0,&all_eei);int count=0;int size=ei;int max=0;for(i=0;isize & count all_emax.w) max=i;printf(%dn,all_emax.w);ret
3、urn 0;Prim#include using namespace std;#define M 2001int setM=0,gMM;char strM8;inline void make_map(int n,int gMM)int i,j,k;for(i=1;i=n;i+)for(j=i+1;j=n;j+)int c=0;for(k=0;k7;k+)if(strik!=strjk) c+;gij=gji=c;int main()int n,qM,qf=0,ql=0,dM,u;char c;scanf(%d%c,&n,&c);int i;while(n!=0)memset(set,0,siz
4、eof(set); memset(g,0,sizeof(g);for(i=1;i=n;i+) scanf(%s,&stri);qi-1=i;di=2000000;qf=0;ql=n-1;make_map(n,g);int sum=0;int f=false;while(qf=ql)int min=qf;for(i=qf+1;i=ql;i+)if(dqi dqmin) min=i;swap(qqf,qmin);u=qqf; qf+;if(f) sum+=du;for(i=1;i=n;i+)if(gui !=0 & gui di) di=gui;f=true;printf(The highest
5、possible quality is 1/%d.n,sum);scanf(%d%c,&n,&c);return 0;堆实现最短路#include #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;w
6、hile(i1 & dhi/2.wdhi.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,in
7、t n,int s) /初始化图和堆int 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;igu.size();i+) relax(d,u,gui.v,gui.w);最短路DIJ普通版#defin
8、e M 101#define LIM 20000000int gMM,dM,fd2MM,gtMM,setM;inline void init(int dM,int n,int s) /初始化图int i;for(i=1;idu+duv)dv=du+duv;void dijkstra(int gMM,int dM,int n,int s) /n is |V| & s is the sourceinit(d,n,s);int qM,ql=1,qf=1; /队列int i;for(i=1;i=n;i+) qql+=i;while(qf!=ql)int min=qf;for(i=qf;iql;i+)
9、if(dqidqmin) min=i; swap(qqf,qmin); /qqf is the minint u=qqf+;for(i=1;i=n;i+)if(gui!=0) relax(d,u,i,gui);floyd#include #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;i=n;i+)for(j=1;j=n;j+)d0ij=gij;d0ii=0; /这里是令d0=gfor(k
10、=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)int t1=k%2; int t2=(t1+1)%2;dt1ij=dt2ij dt2ik+dt2kj?dt2ij:dt2ik+dt2kj;BELL_MANinline void init(int dM,int n,int s) /初始化图int i;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;kn;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(gij!=0) relax(d,i,j,gij);拓扑排序#include
