Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我快WA疯了,求好心的大神和我看看怎么错了,感激不尽(有注释)

Posted by 464271301 at 2013-04-26 17:24:00 on Problem 2337
var t,n,i,x,y,tot,tt,tat,s,cnt:longint;
    head,mark1,mark2:array[-1..30] of longint;
    next,l,num,sta:array[0..5000] of longint;
    v,find:array[0..30] of boolean;
    flag:array[0..5000] of boolean;
    word:array[0..2000] of string;
procedure get(x,y,i:longint);//用一个链表存边,同时排序
var tmp:longint;
begin
  inc(tot);
  next[tot]:=head[x];
  head[x]:=tot;
  l[tot]:=y;
  num[tot]:=i;
  tmp:=tot;
  while next[tmp]<>0 do
  begin
    if word[num[tmp]]>word[num[next[tmp]]] then
    begin
      y:=l[tmp];l[tmp]:=l[next[tmp]];l[next[tmp]]:=y;
      y:=num[tmp];num[tmp]:=num[next[tmp]];num[next[tmp]]:=y;
      tmp:=next[tmp];
    end else break;
  end;
end;

procedure dfsc(x:longint);//用来判断一个图是否连通的
var now:longint;
begin
  find[x]:=true;
  inc(tt);
  now:=head[x];
  while now<>0 do
  begin
    if not find[l[now]] then dfsc(l[now]);
    now:=next[now];
  end;
end;

function check:boolean;//用来判断是否可行
var i,cnt1,cnt2:longint;
begin
  cnt1:=0;cnt2:=0;
  for i:=1 to 26 do
  if mark1[i]>0 then
  begin tt:=0;dfsc(i);s:=i;break;end;
  if tt<>cnt then exit(false);  //这一部分判断是否连通,同时找到到时DFS的第一个点。cnt是总点数,tt是一次DFS找到的总点数

  for i:=1 to 26 do
  begin
    if abs(mark1[i]-mark2[i])>1 then exit(false);
    if mark1[i]-mark2[i]=1 then
    begin inc(cnt1);s:=i;end;
    if mark2[i]-mark1[i]=1 then inc(cnt2);
  end;
 //cnt1是出度-入度大于1的点数,cnt2是入度-出度大于1的点数,同时找到如果是欧拉路径的话搜索的第一个点,mark1是一点的出度,mark2是出度 
  if (cnt1>1) or (cnt2>1) then exit(false);
  if cnt1+cnt2=1 then exit(false);
  exit(true);
end;

procedure dfs(x,e:longint);//用来找路径
var now:longint;
begin
  flag[e]:=true;//flag记录每个点是否被访问。
  now:=head[x];
  while now<>0 do
  begin
    if not flag[now] then
    dfs(l[now],now);
    now:=next[now];
  end;
  inc(tat);sta[tat]:=e;//sta是一个栈,用来存边
end;


procedure main;// 主过程
begin
  fillchar(head,sizeof(head),0);
  fillchar(v,sizeof(v),0);
  fillchar(find,sizeof(find),0);
  fillchar(mark1,sizeof(mark1),0);
  fillchar(mark2,sizeof(mark2),0);
  fillchar(flag,sizeof(flag),0);
  cnt:=0;tot:=0;//各种初始化

  readln(n);
  for i:=1 to n do
  begin
    readln(word[i]);
    x:=ord(word[i][1])-96;
    y:=ord(word[i][length(word[i])])-96;
    get(x,y,i);
    inc(mark1[x]);inc(mark2[y]);

    if not v[x] then begin v[x]:=true;inc(cnt);end;
    if not v[y] then begin v[y]:=true;inc(cnt);end;
  end;

  if not check then
  begin writeln('***');exit;end;

  tat:=0;
  dfs(s,0);
  for i:=tat-1 downto 2 do
  write(word[num[sta[i]]],'.');writeln(word[num[sta[1]]]);

end;




begin
    readln(t);
  while t>0 do
  begin dec(t);main;end;
end.


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator