c++ dfs部落卫队题解

c++ dfs部落卫队题解,第1张

c++ dfs部落卫队题解

1,题目:

 2主要思路:

将m对仇敌关系转化成一张二维关系表(cd[i][j])通过调用表来减少dfs时的时间复杂度。

3代码:

#include 
#include
#include 
using namespace std;
int n,m;
int cd[105][105]={0},rs2[105]={0},rs3[105]={0},max1=0; 
void dfs(int sum,int r){
    if(r>n){
        if(sum>max1){
            max1=sum;
            for(int i=1;i<=n;i++){
                rs3[i]=rs2[i];//将选取的人录入 
            }
        }
        return ;
    }
    int check=1;//定义一个状态参量 
        for(int j=1;j>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;//将仇敌对输入并储存在cd表中 
        cd[x][y]=1;//有仇敌关系则设为1,否则为零 
        cd[y][x]=1;
    }
    dfs(0,1);
    cout< 

4测试数据:

7 10
1 2
1 4
2 4
2 3
2 5
2 6
3 5
3 6
4 5
5 6

3
1 0 1 0 0 0 1

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5651449.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存