问题标题: 请问酷町堂1052题 部落卫队 Wrong Answer:0分 请各位大佬帮帮忙。

0
0
已解决
栾峻岩
栾峻岩
初级天翼
初级天翼
#include <iostream>
using namespace std; 
int n,m;            
struct choudi
{
    int a,b;
}c[200];  
bool cd[200][200];  
int cd2[200];
int maxx;   
int ans[200];
bool used[200];
void dfs(int t)
{
    if (t>n)
    {
        int v=0;
        for (int i=1;i<=n;i++)
            if (ans[i])
                v++;
        if (maxx<v)
        {
            maxx=v;
            for (int i=1;i<=n;i++)
                cd2[i]=ans[i];
        }       
    }
    for (int i=1;i<=n;i++)
    {
        if (!used[i] && !cd[i][i-1] )
        {
            used[i]=true;
            ans[t]=i;
            dfs(t+1);
            used[i]=false;
            ans[t]=0;
        }
    }
}
int main() 
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>c[i].a>>c[i].b;
        cd[c[i].a][c[i].b]=true;
    }
//  for (int i=1;i<=n;i++)
//  {
//      for (int j=1;j<=n;i++)
//      {
//          if (cd[i][j])
//              cout<<"在这个群落中,"<<"第"<<i<<"个人和第"<<j<<"个人是仇敌关系"<<endl; 
//      }
//  }
    dfs(1);
    cout<<maxx<<endl;
    for (int i=1;i<=n;i++)
        cout<<cd2[i]<<" ";
    cout<<endl; 
    return 0;
}

请各位大佬帮帮忙。

网址:

1052   部落卫队

测试点#1测评结果 : Wrong Answer时间 : 0ms

测试点#2测评结果 : Wrong Answer时间 : 0ms

测试点#3测评结果 : Time Limit Exceeded时间 : 1996ms

测试点#4测评结果 : Time Limit Exceeded时间 : 2000ms

测试点#5测评结果 : Time Limit Exceeded时间 : 2004ms

测试点#6测评结果 : Time Limit Exceeded时间 : 1992ms

题目:

原始部落byteland中的居民们为了争夺有限的资源,经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍,希望从部落的居民中选出最多的居民入伍,并保证队伍中任何2 个人都不是仇敌。 给定byteland部落中居民间的仇敌关系,编程计算组成部落卫队的最佳方案。

输入描述 Input Description

第1行有2个正整数n和m,表示byteland部落中有n个居民,居民间有m个仇敌关系。居民编号为1,2,…,n。接下来的m行中,每行有2个正整数u和v,表示居民u与居民v是仇敌。

输出描述 Output Description

第1行是部落卫队的人数;文件的第2行是卫队组成xi,1≤i≤n,xi =0 表示居民i不在卫队中,xi=1表示居民i在卫队中。

样例输入 Sample Input

 

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

样例输出 Sample Output

3
1 0 1 0 0 0 1


1
已采纳
蒋智航
蒋智航
高级天翼
高级天翼

用多个数组储存仇敌关系、选择方案,并且用搜索

1
0
0
0
0
0
我要回答