部落卫队问题
pascal吧
全部回复
仅看楼主
level 1
大扫比 楼主
用回溯算法
部落卫队问题
1

问题描述;
原始部落
byteland
中的居民们为了争夺有限的资源,
经常发生冲
突。
几乎每个居民都有他的仇敌。
部落酋长为了组织一支保卫部落的队伍,
希望
从部落的居民中选出最多的居民入伍,并保证队伍中任何
2
个人都不是仇敌。
2

算法设计;
给定
byteland
部落中居民间的仇敌关系,
计算组成部落卫队的最
佳方案
3
、数据输入;由文件
input.txt
给出输入数据。第一行有两个正整数
n

m

表示
byteland
部落中有
n
个居民,
居民间有
m
个仇敌关系。
居民编号为
1

2

…,n。
接下来的
m
行中,每行有
2
个正整数
u

v
,表示居民
u

v
是仇敌
4
、结果输出;将计算的部落卫队的最佳方案输出到文件
output.txt
。文件的第
一行是部落卫队的人数;第二行是部落卫队组成
Xi
,1≤i≤n。
Xi=0
表示居民
i
不在卫队中,
Xi=1
表示居民在卫队中
2014年12月20日 09点12分 1
level 1
大扫比 楼主
var a:array [1..5000] of longint;
chou,b:array [1..100,1..100] of longint;
b:array [1..100,1..100] of bealoon;
i,n,j,k,l:longint;
procedure try(x:longint;);
var i:=longint;
begin
if x=n+1 then
begin
if b[i,l]=false then begin a[b]:=1; inc(k); end;
exit;
end;
for i:=1 to n do
?????????????????????????????????????
begin
if
end;
end;
begin
read(m,n);
a[i]:=0;
for i:=1 to m do
read(chou[j,k]);
b[j,k]:=true;
b[k,j]:=true;
try(1);
write(k);
writeln(a[i]);
end.
在问号处应该怎么加,其它地方的错误怎么改
2014年12月20日 09点12分 2
level 1
参考程序:
program Project1;
type
cd=record
u,v:integer;
end;
var
dd:array[1..100] of cd;
f:array[0..100] of boolean;
n,m,x,i:integer;
procedure wd(i:integer);
var
ans,j:integer;
begin
if i>n then
begin
ans:=0;
for j:=1 to n do
if f[j] then inc(ans);
if ans>x then x:=ans;
exit;
end;
f[0]:=true;
for j:=1 to m do
if ((i=dd[j].u) and f[dd[j].v]) or ((i=dd[j].v) and f[dd[j].u]) then
begin
f[0]:=false;
break;
end;
if f[0] then
begin
f[i]:=true;
wd(i+1);
f[i]:=false;
end;
wd(i+1);
end;
begin
readln(n,m);
for i:=1 to m do
with dd[i] do
readln(u,v);
wd(1);
writeln(x);
readln;readln;
end.
2015年02月19日 07点02分 3
1