ACM算法集锦

kurXX最小生成树#include <iostream>#include <math.h>#include <algorithm>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.w<b.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(setb!=0) b=setb;bc+;if(b2!=b) setb2=b; if(a=b) return false;if(ac<bc) seta=b;else setb=a;return true;int main()int i,j,k,n,m,u,v,t;cin >> t;for(k=0;k<t;k+)memset(set,0,sizeof(set);cin >> 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(i<j)all_eei+=e;sort(&all_e0,&all_eei);int count=0;int size=ei;int max=0;for(i=0;i<size && count < n-1;i+)if(uni(set,all_ei.u,all_ei.v)count+;if(all_ei.w>all_emax.w) max=i;printf("%dn",all_emax.w);return 0;Prim#include <iostream>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;k<7;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,sizeof(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 possible quality is 1/%d.n",sum);scanf("%d%c",&n,&c);return 0;堆实现最短路#include <iostream>#include <string>#include <stdlib.h>#include <vector>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<node> gM,g2M;void change_key(dd dM,int v,int w)dv.w=w;int i=dv.q;while(i>1 && dhi/2.w>dhi.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 (l<=s && dai.w>dal.w)miner = l;else miner=i;if (r<=s && daminer.w>dar.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) /初始化图和堆int i;hs=n;for(i=1;i<=n;i+)di.w=LIM;hi=di.q=i;change_key(d,s,0);inline void relax(dd dM,int u,int v,int duv)if(dv.w>du.w+duv) change_key(d,v,du.w+duv);void dijkstra(vector<node> 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;i<gu.size();i+) relax(d,u,gui.v,gui.w);最短路DIJ普通版#define M 101#define LIM 20000000int gMM,dM,fd2MM,gtMM,setM;inline void init(int dM,int n,int s) /初始化图int i;for(i=1;i<=n;i+)di=LIM;ds=0;inline void relax(int dM,int u,int v,int duv)if(dv>du+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;i<ql;i+) if(dqi<dqmin) 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 <iostream>#include <vector>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=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;i<=n;i+)di=2000000000;ds=0;inline void relax(int dM,int u,int v,int duv)if(dv>du+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<n;k+)for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(gij!=0) relax(d,i,j,gij);拓扑排序#include <iostream>