UOJ Logo admin的博客

博客

#97. 部落卫队题解 (错误更正)

2018-03-14 00:09:01 By admin

讲课时的错误在哪里?

按照之前的方案,例如1号的敌人有5,5号被标记为-1,如果2号的敌人也有5,5号被重复被标记为-1,但在2号递归结束回溯的时候,5号就被反标记为0,其实这时候5号应该仍然是-1,因为它还是1号的敌人,不能被直接置0。

bx[k]=1;
for(int i=k+1; i<=n; i++)
    if(mt[i][k]) bx[i]=-1;        //标记k号的敌人为-1
search(n, k+1);
bx[k]=-1;
for(int i=k+1; i<=n; i++)
    if(mt[i][k]) bx[i]=0;        //标记k号的敌人为0,这里是出错的地方,因为i号可能是小于k的某人的敌人,可能需要保持-1

所以,偷懒少设置一个数组并不好,省了丁点儿空间却增加了复杂度,用1,0,-1三种状态来标记增加了出错的机率,实在是得不偿失!!!

因此,更好的方案就是新设置一个数组bj[]用于标记状态和回溯,敌对关系不用1表示,而是用计数的方式表示,如果在某个时候i是k的敌人,那么bj[i]++,回溯的时候bj[i]--,如果bj[i]==0,说明i和目前选中的人都不是敌人,这样就避免了上课时犯的错误。


  • 下面是AC代码,一些变量名字做了调整,请认真阅读注释,如果有不明白的地方,评论区@admin或者直接问我。

  • 为上课犯这样一个错误耽误大家时间向你们致歉,也期望大家更加认真,吸取教训!

  • 宁可多几个变量,宁可多一些空间,千万不要以逻辑复杂度的提高来换取微不足道的空间和时间优化。

#include<iostream>
#include<algorithm>
using namespace std;
int n, m, ans=0;
bool mt[1000][1000];                    //以二维矩阵记录仇敌关系
int  p[1000];                            //p[i]=1表示i被选,=0表示未被选
int  pp[1000];                            //存储ans最大时的方案(p数组),用于输出
int  bj[1000];                            //标记数组,用于回溯,bj[i]==0表示i目前没有敌人,可以被选
void search(int n, int k, int rs){        //rs为当前被选的总人数,rs和n也可以设置为全局变量
    if(n+1==k){                            //递归终止条件
        if(rs>ans){                        //更新ans和pp数组
            ans=rs;
            copy(p+1, p+1+n, pp+1);     //复制p[1...n]到pp[1...n],这种写法更C++
        }
        return ;
    }
    if(rs+n-k+1<ans) return;            //预测当前可能的最大选择人数,如果小于当前ans,无需递归,这是一个重要的剪枝条件
    if(!bj[k]){                            //目前被选的人中没有k号的敌人,故可以选择k
        p[k]=1;                            //选中k
        for(int i=k+1; i<=n; i++)        //在bj[k+1...n]中标记k的敌人
            if(mt[i][k]) bj[i]++;        //因为一个人可能为多个人的敌人,故用计数的方式标记
        search(n, k+1, rs+1);            //递归到下一个人
        for(int i=k+1; i<=n; i++)        //回溯,在bj[k+1...n]中标记k的敌人反标记
            if(mt[i][k]) bj[i]--;        //只是取消bj[i]和k的敌对状态,但bj[i]可能和别人还是敌对状态
    }
    p[k]=0;                                //不选k
    search(n, k+1, rs);                    //递归到下一个人
}
int main(){
    cin>>n>>m;
    for(int i=0; i<m; i++){                //读入m个敌对关系
        int u, v;
        cin>>u>>v;
        mt[u][v]=mt[v][u]=true;
    }
    search(n, 1, 0);
    cout<<ans<<endl;
    for(int i=1; i<=n-1; i++)
        cout<<pp[i]<<" ";
    cout<<pp[n]<<endl;                    //数据格式要求,最后一个数字后不能有空格
    return 0;
}

评论

King_Nengneng
前排滋滋
goddess_Q
@@@@@@@@@@@@@@@@@@美滋滋
Eien
^-^

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。