ACM算法集锦

ACM算法资料集锦2009年12月10日星期四1kurXX最小生成树#includeiostream#includemath.h#includealgorithmusingnamespacestd;#defineM501#defineLIM20000000structedg{intu,v;intw;}all_e[M*M/2];booloperator(constedg&a,constedg&b){returna.wb.w;}intset[M];inlinebooluni(intset[],inta,intb){intac=0,a2=a,b2=b,bc=0;while(set[a]!=0){a=set[a];ac++;}if(a2!=a)set[a2]=a;while(set[b]!=0){b=set[b];bc++;}if(b2!=b)set[b2]=b;if(a==b)returnfalse;if(acbc)set[a]=b;elseset[b]=a;returntrue;}intmain(){inti,j,k,n,m,u,v,t;cint;for(k=0;kt;k++){memset(set,0,sizeof(set));cinn;intei=0;for(i=1;i=n;i++){for(j=1;j=n;j++){if(t!=0){edge;e.u=i;e.v=j;scanf(%d,&e.w);if(ij)all_e[ei++]=e;}}}sort(&all_e[0],&all_e[ei]);intcount=0;intsize=ei;intmax=0;for(i=0;isize&&countn-1;i++){if(uni(set,all_e[i].u,all_e[i].v)){count++;if(all_e[i].wall_e[max].w)max=i;}}printf(%d\n,all_e[max].w);}return0;}Prim#includeiostreamusingnamespacestd;#defineM2001intset[M]={0},g[M][M];charstr[M][8];inlinevoidmake_map(intn,intg[M][M]){inti,j,k;for(i=1;i=n;i++){for(j=i+1;j=n;j++){intc=0;for(k=0;k7;k++)if(str[i][k]!=str[j][k])c++;g[i][j]=g[j][i]=c;}}}intmain(){intn,q[M],qf=0,ql=0,d[M],u;charc;scanf(%d%c,&n,&c);inti;while(n!=0){memset(set,0,sizeof(set));memset(g,0,sizeof(g));for(i=1;i=n;i++){scanf(%s,&str[i]);q[i-1]=i;d[i]=2000000;}qf=0;ql=n-1;make_map(n,g);intsum=0;intf=false;ACM算法资料集锦2009年12月10日星期四2while(qf=ql){intmin=qf;for(i=qf+1;i=ql;i++){if(d[q[i]]d[q[min]])min=i;}swap(q[qf],q[min]);u=q[qf];qf++;if(f)sum+=d[u];for(i=1;i=n;i++){if(g[u][i]!=0&&g[u][i]d[i])d[i]=g[u][i];}f=true;}printf(Thehighestpossiblequalityis1/%d.\n,sum);scanf(%d%c,&n,&c);}return0;}堆实现最短路#includeiostream#includestring#includestdlib.h#includevector;usingnamespacestd;#defineM1001#defineLIM2000000000structdd{//最短距离intw,q;//w是距离值,q是堆中的相对位置}d[M],d2[M];structnode{intv,w;};inth[M],hs;vectornodeg[M],g2[M];voidchange_key(ddd[M],intv,intw){d[v].w=w;inti=d[v].q;while(i1&&d[h[i/2]].wd[h[i]].w){swap(h[i],h[i/2]);swap(d[h[i]].q,d[h[i/2]].q);i=i/2;}}inlinevoidmin_heaphy(ddd[M],int*a,inti,ints){//s为堆大小intl=i*2,r=i*2+1;intminer=i;if(l=s&&d[a[i]].wd[a[l]].w)miner=l;elseminer=i;if(r=s&&d[a[miner]].wd[a[r]].w)miner=r;if(miner!=i){swap(a[i],a[miner]);swap(d[a[i]].q,d[a[miner]].q);min_heaphy(d,a,miner,s);}}inlinevoidinit(ddd[M],intn,ints){//初始化图和堆inti;hs=n;for(i=1;i=n;i++){d[i].w=LIM;h[i]=d[i].q=i;}change_key(d,s,0);}inlinevoidrelax(ddd[M],intu,intv,intduv){if(d[v].wd[u].w+duv)change_key(d,v,d[u].w+duv);}voiddijkstra(vectornodeg[M],ddd[M],intn,ints){//nis|V|&&sisthesourceinit(d,n,s);inti;while(hs!=0){intu=h[1];swap(h[1],h[hs]);swap(d[h[1]].q,d[h[hs]].q);hs--;min_heaphy(d,h,1,hs);for(i=0;ig[u].size();i++)relax(d,u,g[u][i].v,g[u][i].w);}}最短路DIJ普通版#defineM101#defineLIM20000000intg[M][M],d[M],fd[2][M][M],gt[M][M],set[M];inlinevoidinit(intd[M],intn,ints){//初始化图inti;for(i=1;i=n;i++)d[i]=LIM;d[s]=0;}inlinevoidrelax(intd[M],intu,intv,intduv){ACM算法资料集锦2009年12月10日星期四3if(d[v]d[u]+duv)d[v]=d[u]+duv;}voiddijkstra(intg[M][M],intd[M],intn,ints){//nis|V|&&sisthesourceinit(d,n,s);intq[M],ql=1,qf=1;//队列inti;for(i=1;i=n;i++)q[ql++]=i;while(qf!=ql){intmin=qf;for(i=qf;iql;i++)if(d[q[i]]d[q[min]])min=i;swap(q[qf],q[min]);//q[qf]istheminintu=q[qf++];for(i=1;i=n;i++){if(g[u][i]!=0)relax(d,u,i,g[u][i]);}}}floyd#includeiostream#includevectorusingnamespacestd;#defineM301#defineLIM200000000intw[M][M],d[2][M][M];voidfloyd(intg[M][M],intd[2][M][M],intn){inti,j,k;for(i=1;i=n;i++){for(j=1;j=n;j++){d[0][i][j]=g[i][j];}d[0][i][i]=0;}//这里是令d[0]=gfor(k=1;k=n;k++){for(i=1;i=n;i++)for(j=1;j=n;j++){intt1=k%2;intt2=(t1+1)%2;d[t1][i][j]=d[t2][i][j]d[t2][i][k]+d[t2][k][j]?d[t2][i][j]:d[t2][i][k]+d[t2][k][j];}}}BELL_MANinlinevoidinit(intd[M],intn,ints){//初始化图inti;for(i=1;i=n;i++)d[i]=2000000000;d[s]=0;}inlinevoidrelax(intd[M],intu,intv,intduv){if(d[v]d[u]+duv)d[v]=d[u]+duv;}voidbell_man(intg[M][M],intd[M],intn,ints){//n个结点s为源点inti,j,k;init(d,n,s);for(k=1;kn;k++){for(i=1;i=n;i++)for(j=1;j=n;j++){if(g[i][j]!=0)relax(d,i,j,g[i][j]);}}}拓扑排序#includeiostream#includestack#includevector#includelistusingnamespacestd;vectorintorder;voidfind_id(listintg[],intid[],intn){//寻找入度,没有使用inti;listint::iteratork;for(i=0;in;i++){for(k=g[i].begin();k!=g[i].end();k++){id[*k]++;}}}voidtopo(listintg[],intid[],intn,bool&OK,bool&incon){//OK==false表示未确定顺序incon==true表示发现矛盾stackints;order.erase(order.begin(),order.end());intt[26];copy(&id[0],&id[n],&t[0]);inti;for(i=0;in;i++){if(id[i]==0)s.push(i);}if(s.size()!=1)OK=false;intcount=0;ACM算法资料集锦2009年12月10日星期四4while(!s.empty()){intv=s.top();s.pop();count++;order.push_back(v);listint::iteratork;for(k=g[v].begin();k!=g[v].end();k++){id[*k]--;if(id[*k]==0)s.push(*k);if(s.size()1)OK=false;}}if(order.size()n)OK=false;//矛盾发生,会导致这种情况,小心if(countn)incon=true;copy(&t[0],&t[n],&id[0]);}DFS强连通分支#includeiostream#includealgorithm#includevectorusingnamespacestd;#defineM20005vectorintg[M],gt[M];boolused[M];intft[M],sort_v[M],tim;boolcomp(constint&u,constint&v){returnft[u]ft[v];}inlineintfin