acm集成代码

各种背包voidZoreOnePack(intcost,intweight){for(inti=W;i=weight;--i)f[i]=max(f[i],f[i-weight]+cost);}voidCompletePack(intcost,intweight){for(inti=weight;i=W;++i)f[i]=max(f[i],f[i-weight]+cost);}voidMultiPack(intcost,intweight,intnum){if(num*weight=W)CompletePack(cost,weight);else{intk=1;while(knum){ZoreOnePack(cost*k,weight*k);num-=k;k+=k;}ZoreOnePack(cost*num,weight*num);}}voidTwoZoreOnePack(intcost,intweight,intmany){for(inti=W;i=weight;--i)for(intj=M;j=many;--j)two[i][j]=max(two[i][j],two[i-weight][j-many]+cost);}voidTwoCompletePack(intcost,intweight,intmany){for(inti=weight;i=W;++i)for(intj=many;j=W;++j)two[i][j]=max(two[i][j],two[i-weight][j-many]+cost);}voidTwoMultiPack(intcost,intweight,intmany,intnum){if(num*weight=W&&num*many=M)TwoCompletePack(cost,weight,many);else{intk=1;while(knum){TwoZoreOnePack(cost*k,weight*k,many*k);num-=k;k+=k;}TwoZoreOnePack(cost*num,weight*num,many*num);}}//johnson流水作业算法#includeiostream#includealgorithmusingnamespacestd;constintMax=100;intc[Max],a[Max],b[Max],i,j,k,n;classJob{public:intkey,index;}job[Max];boolcomp(Jobp,Jobq){returnp.key=q.key;}intmain(){while(cinn){for(i=0;in;++i){scanf(%d%d,&a[i],&b[i]);job[i].key=min(a[i],b[i]);job[i].index=i;}sort(job,job+n,comp);j=0;k=n-1;for(i=0;in;++i)if(a[i]=b[i])c[j++]=job[i].index;elsec[k--]=job[i].index;j=a[c[0]];k=j+b[c[0]];for(i=1;in;++i){j+=a[c[i]];k=jk?k+b[c[i]]:j+b[c[i]];}coutkendl;}return0;}//矩阵连乘#includeiostreamusingnamespacestd;constintMax=1000;intresult[Max][Max],a[Max],n;voidmatrix(){for(inti=1;i=n;++i)result[i][i]=0;for(intj=2;j=n;++j)for(inti=j-1;i0;--i){result[i][j]=result[i][j-1]+a[i-1]*a[j-1]*a[j];for(intk=j-2;k=i;--k){intmin=result[k+1][j]+result[i][k]+a[i-1]*a[k]*a[j];if(minresult[i][j])result[i][j]=min;}}}voidoutput(){for(inti=1;i=n;++i){for(intj=1;j=n;++j){cout.width(6);coutresult[i][j];}coutendl;}}intmain(){while(cinn){for(inti=0;i=n;++i)cina[i];matrix();output();coutresult[1][n]endl;}return0;}//BigNumber大数乘法constintMax=1000,intUnit=10000,intU=4;classBigNum{public:intnum[Max],length;boolflag;BigNum(){memset(num,0,sizeof(num));};BigNum(stringstr);voidout();};BigNum::BigNum(stringstr){if(str[0]=='-'){flag=false;str=str.substr(1);}elseflag=true;intlen=str.size()-1,j,k,i=len;length=len/U+1;memset(num,0,sizeof(num));while(i=0){j=(len-i)/U;for(k=1;kUnit&&i=0;k*=10,--i)num[j]+=(str[i]-'0')*k;}}voidBigNum::out(){if(!flag)printf(-);inti=length-1;while(i=0&&num[i]==0)--i;if(i0){cout0;return;}printf(%d,num[i--]);for(;i=0;--i){cout.width(U);cout.fill('0');coutnum[i];}}BigNummulti(BigNum&a,BigNum&b){BigNumc;c.flag=a.flag==b.flag;c.length=a.length+b.length;intk=0,len=c.length;for(inti=0;ia.length;++i){for(intj=0;jb.length;++j)c.num[i+j]+=a.num[i]*b.num[j];k=0;for(inte=0;elen;++e){c.num[e]+=k;k=c.num[e]/Unit;c.num[e]%=Unit;}while(k){c.num[c.length]=k%Unit;k/=Unit;++c.length;}}returnc;}贪心法找最短路径问题#includeiostream#includealgorithmusingnamespacestd;constintMax=1000;constintBig=1000000;intprov,map[Max][Max],n,m,dist[Max],start,end,i,temp;booluse[Max];voidinput(){intx,y,d;memset(map,127,sizeof(map));memset(use,0,sizeof(use));for(x=0;x=n;++x)map[x][x]=0;for(inti=0;im;++i){scanf(%d%d%d,&x,&y,&d);map[x][y]=map[y][x]=d;}scanf(%d%d,&start,&end);}voidrun(){for(i=1;i=n;++i)dist[i]=map[start][i];use[start]=true;while(!use[end]){temp=Big;for(i=1;i=n;++i){if(!use[i]&&tempdist[i]){temp=dist[i];prov=i;}}use[prov]=true;for(i=1;i=n;++i)if(!use[i])dist[i]=min(dist[i],map[prov][i]+temp);}}intmain(){while(scanf(%d%d,&n,&m)!=EOF){input();run();printf(%d\n,dist[end]);}return0;}//最短路径问题集成算法#includeiostream#includevector#includequeueusingnamespacestd;constintMax=10005;intdist[Max];boolpass[Max];vectorpairint,intedge[Max];#definemake_edge(u,v,value)edge[u].push_back(make_pair(v,value))inlinevoidrun(ints,intn){for(inti=1;i=n;++i)dist[i]=20000000,pass[i]=0;pass[s]=1,dist[s]=0;queueintq;q.push(s);while(!q.empty()){intcurr=q.front();q.pop();intsize=edge[curr].size();for(inti=0;isize;++i){intnext=edge[curr][i].first;intd=dist[curr]+edge[curr][i].second;if(ddist[next]){dist[next]=d;if(pass[next]==0){pass[next]=1;q.push(next);}}}Pass[curr]=0;}}intmain(){intn,m,i,s,e,d;while(scanf(%d%d,&n,&m)!=EOF){for(inti=0;im;++i){scanf(%d%d%d,&s,&e,&d);make_edge(s,e,d);make_edge(e,s,d);}scanf(%d%d,&s,&e);run(s,n);printf(%d\n,dist[e]);}return0;}//宽搜单源最短路径#includeiostream#includequeueusingnamespacestd;constintMax=1000,intMax_road=100000;intnode_num,link_num,min_road,road[Max][Max],start,end;booluse[Max],link[Max][Max];classNode{public:intnode,road;Node(intn,intr){node=n;road=r;}Node(){}};booloperator(Nodea,Nodeb){returna.roadb.road;}priority_queueNodepqi;voidinput(){inta,b,r;memset(use,false,sizeof(use));memset(link,false,sizeof(link));while(link_num--){scanf(%d%d%d,&a,&b,&r);road[a][b]=road[b][a]=r;link[a][b]=link[b][a]=true;}min_road=Max_road;scanf(%d%d,&start,&end);}voidrun(){pqi.push(Node(start,0));Noden;while(!pqi.empty()){n=pqi.top();pqi.pop();if(use[n.node])continue;if(n.road=