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;
}
请各位大佬帮帮忙。
网址:
测试点#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