unit1.~pas

二分覆盖算法的贪婪算法解决。使用dephi编译。使用了贪婪算法。

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Edit2: TEdit;
    Memo1: TMemo;
    Memo2: TMemo;
    Button1: TButton;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Label4: TLabel;
    Edit3: TEdit;
    Edit4: TEdit;
    Label5: TLabel;
    Label6: TLabel;
    procedure input;
    procedure cover;
    procedure output;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

type
  pointsetA=Record
    degree:integer;
    no:string;
  end;
type
  pointsetB=Record
    select:boolean;
    no:string;
  end;

var
  Form1: TForm1;
  m,n:integer;
  A:array of pointsetA;
  B:array of pointsetB;
  AB:array of array of integer;
  selectA:array of string;


implementation

{$R *.dfm}

procedure TForm1.input;
var
i,j,comma:integer;
str,substr:string;
begin
m:=strtoint(edit1.Text);
n:=strtoint(edit2.Text);
setlength(A,m);
setlength(B,n);
setlength(AB,m,n);
setlength(selectA,m);
for i:=0 to m-1 do
selectA[i]:='';
str:=edit3.Text;
for i:=0 to m-1 do
begin
comma:=pos(',',str);
if (comma=0) then comma:=length(str)+1;
substr:=copy(str,1,comma-1);
A[i].no:=substr;
substr:='';
delete(str,1,comma);
end;
str:=edit4.Text;
for i:=0 to n-1 do
begin
comma:=pos(',',str);
if (comma=0) then comma:=length(str)+1;
substr:=copy(str,1,comma-1);
B[i].no:=substr;
substr:='';
delete(str,1,comma);
end;
for i:=0 to m-1 do
begin
str:=memo1.Lines[i];
for j:=0 to n-1 do
begin
comma:=pos(',',str);
if (comma=0) then comma:=length(str)+1;
substr:=copy(str,1,comma-1);
AB[i,j]:=strtoint(substr);
substr:='';
delete(str,1,comma);
end;
end;
for i:=0 to m-1 do
for j:=0 to n-1 do
if (AB[i,j]<>0) then
A[i].degree:=A[i].degree+1;
for i:=0 to n-1 do
B[i].select:=false;

end;

procedure TForm1.cover;
var
i,j,max,t:integer;
flag,flag2:boolean;
begin
flag:=false;
flag2:=false;
t:=0;
repeat
begin
max:=0;
for i:=0 to m-1 do
if max<A[i].degree then
begin
max:=A[i].degree;
t:=i;
end;
selectA[t]:=A[t].no;
for j:=0 to n-1 do
if (AB[t,j]<>0)and(not B[j].select) then
begin
B[j].select:=true;
for i:=0 to m-1 do
if (AB[i,j]<>0)and(A[i].degree>0) then A[i].degree:=A[i].degree-1;
end;
flag:=true;
for i:=0 to m-1 do
begin
if A[i].degree=0 then flag2:=true
else flag2:=false;
flag:=(flag and flag2);
end;
end;
until flag;
end;

procedure TForm1.output;
var
i:integer;
flag:boolean;
begin
memo2.Clear;
flag:=true;
for i:=0 to n-1 do
flag:=flag and B[i].select;
if flag then
begin
for i:=0 to m-1 do
memo2.Lines.Add(selectA[i]);
end
else memo2.Lines.Add('null');
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
input;
cover;
output;
end;

end.