经典ACM算法合集经典ACM算法合集(15)

2> 当i>n时循环结束；
③ return 1；
c. 用递归函数cut(i, s) 来实现回溯法搜索子集树（形式参数i表示递归深度，n用
来控制递归深度，形式参数s表示当前顶点权之和）：
① 若s>=bestw，则不是最优解，剪去相应子树，返回到i-1层继续执行；
② 若i >n，则算法搜索到一个叶结点，调用函数cover()对图G进行判断：
若cover()为真，则用bestw对最优解进行记录，返回到i-1层继续执行；
③ 对顶点i分在与不在顶点覆盖集中两种情况进行讨论：
1> 若顶点i不在顶点覆盖集中（即c[i]==0），则调用函数cut(i+1,s)；
2> 若顶点i在顶点覆盖集中（即c[i]==1），则调用函数cut(i+1,s+w[i])；
④ 当i=1时，若已测试完所有顶点覆盖方案，外层调用就全部结束；
d. 主函数调用一次cut(1,0)即可完成整个回溯搜索过程，最终得到的bestw即为所
求最小顶点权之和。

4、源程序：

#include<stdio.h>
#define MIN 100000
int m,n,u,v,bestw;
int e[100][100],w[100],c[100];

int cover()
{
int i,j,t;
i=1;
while (i<=n)
{
t=0;
if(c[i]==0)
{
j=1;
while(j<i)
{
if(e[j][i]==1&&c[j]==1)
t=1;
j++;
}
j++;
while(j<=n)
{
if(e[i][j]==1&&c[j]==1)
t=1;
j++;
}
if(t==0)
return 0;
}
i++;
}
return 1;
}

void cut(int i,int s)
{
if(s>=bestw)
return;
if(i>n)
{
if(cover())
bestw=s;
return;
}
c[i]=0;
cut(i+1,s);
c[i]=1;
cut(i+1,s+w[i]);
}

main()
{
int i,j,k;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&w[i]);
c[i]=0;

}

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
e[i][j]=0;

for(k=1;k<=m;k++)
{
scanf("%d%d",&u,&v);
e[u][v]=1;
}

bestw=MIN;
cut(1,0);
printf("%d",bestw);
return 0;
}



5、算法分析：
函数cover
()的双重while循环的时间复杂度为，递归函数cut(i, s)遍历子集
树的时间复杂度为，且函数cover()嵌套在函数cut(i, s)内，所以递归函数cut(i, s)
的时间复杂度为；主函数的双重for循环的复杂度为，且主函数调用
递归函数cut(1, 0)，故该算法的时

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科经典ACM算法合集经典ACM算法合集(15)全文阅读和word下载服务。