C++常用经典算法及其实现

C++常用经典算法及其实现

(总20页)-CAL-FENGHAI.-(YICAI)-CompanyOne1-CAL-本页仅作为文档封面，使用请直接删除#qsort(1,t);//对t条边按权值大小按从小到大的次序进行快速排序for(inti=1;i<=t;i++){intx1=getfather(elist[i].from);//取第i条边的起点所在的树的根intx2=getfather(elist[i].to);//取第i条边的终点所在的树的根if(x1!=x2){sum++;merge(x1,x2);ans十=elist[i].w;}//不在同一个集合，合并，即第i条边可以选取。if(sum>n-1)break;//已经确定了口-1条边了，最小生成树已经生成了，可以提前退出循环了}if(sum<n-1)cout<<"Impossible"<<endl;//从t条边中无法确定n-1条边，说明无法生成最小生成树elsecout<<ans<<endl;}克鲁斯卡尔算法，只用了边集数组，没有用到图的邻接矩阵，因此当图的结点数比较多的时候，输入数据又是边的信息时，就要考虑用Kruscal算法。对于岛国问题，我们就要选择此算法，如果用Prim算法，还要开一个二维的数组来表示图的邻接矩阵，对于10000个点的数据，显然在空间上是无法容忍的。二十一、Floyed算法voidfloyed(void)//a[i][j]表示结点i到结点j的最短路径长度，初始时值为<IJ>的权值。{for(intk=1;k<=n;k++)〃枚举中间加入的结点不超过K时f[i][j]最短路径长度，K相当DP中的阶段for(inti=1;i<=n;i++)//i，j是结点i到结点J，相当于DP中的状态for(intj=1;j<=n;j++)if(a[i][j]>a[i][k]+a[k][j])a[i][j]=a[i][k]+a[k][j];//这是决策，加和不加中间点，取最小的值}弗洛伊德算法适合于求没有负权回路的图的最短路径长度，利用FLOYED算法，可写出判断结点i和结点J是否连通的算法。二十二、01背包问题n为物品的数量，w[i]表示第i个物品的重量，c[i]表示第i个物品的价值，v为背包的最大重量。有状态转移方程f[i]j]=max{f[i-1]j],f[i-1]j-w[i]]+c[i]}。f[i][j]表示前i个物品，在背包载重为j时获得的最大价值。显然f[n][v]即为所求。边界条件为f[0][s]=0,s=0,1，…,v。for(inti=1;i<=n;i++)//枚举阶段for(int)=0力<=丫力++)//枚举状态，当然此处也可写成：for(intj=v;j>=0;j--){f[i][j]=f[i-1][j];//不选第i个物品if(f[i][j]<f[iT][j-w[i]]+c[i])f[i][j]=f[iT][j-w[i]]+c[i];//选第i个物品}cout<<f[n][v]<<endl;//输出结果。优化：用一维数组实现，把第i-1阶段和第i阶段数据存在一块。for(inti=1;i<=n;i++)//枚举阶段for(intj=丫力>=0力一)//枚举状态，当然此处也可写成:for(intj=v;j>=0;j--){f[j]=f[j];//不选第i个物品，可省略此语句。if((j>w[i])&&(f[j]<f[j-w[i]]+c[i]))f[j]=f[j-w[i]]+c[i];〃选第i个物品}cout<<f[v]<<endl;//输出结果。对比优化前后，我们不难发现，优化后的代码实际上就是在原来基本的代码基础上，减少了阶段这一维，同时在枚举状态时，为了保证结果的正确性，枚举的顺序只能是v到0，而不能是0到v。大家细想一下为什么？就是保证在求第i阶段j状态时，f[j-w[i]]为第i-1阶段的值。进一步优化，在上面代码中，枚举状态时，还可以写成for(intj=vj>=w[i]j--)，此时下面的判断条件j>=w[i]就可以省略了。二十三、完全背包问题和01背包问题不同的是，完全背包，对于任何一个物品i,只要背包重量允许，可以多次选取，也就是在决策上，可以选0个，1个，2个，…，v/w[i]个。状态转移方程f[i][j]=max{f[i-1][j],f[i-1][j-w[i]]+c[i]，f[i-1][j-2*w[i]]+2*c[i]，…，f[i-1][j-k*w[i]]+k*c[i]}。k=0，1,2,…，v/w[i]。f[i][j]表示前i个物品，在背包载重为j时获得的最大价值。显然f[n][v]即为所求。边界条件为f[0][s]=0,s=0,1，…,v。for(inti=1;i<=n;i++)//枚举阶段for(int)=0力<=丫力++)//枚举状态，当然此处也可写成：for(intj=v;j>=0;j--){f[i][j]=f[i-1][j];//k=0的情况作为f[i][j]的初始值，然后在k=1,2，…,v/w[i]中找最大值for(intk=1;k<=v/w[i];k++)if(f[i][j]<f[i-1][j-k*w[i]]+k*c[i])f[i][j]=f[i-1][j-k*w[i]]+k*c[i];/选第i个物品}cout<<f[n][v]<<endl;//输出结果。二十四、多属性背包问题二十五、多背包问题二十六、最长不降(上升)子序列问题f[i]表示从第1个数开始，以第i个数结尾的最长递增子序列。状态转移方程：f[i]=max{f[j]}+1(1WjWiT,1WiWn,a[i]三a[j])临界状态：f[1]=1；二十七、最长公共子序列问题f[i][j]表示第一个串前i