回 帖 发 新 帖 刷新版面

主题:[讨论]关于一笔画问题

const n=6;
var  a:array[1..n,1..n]of integer;
     b:array[1..n]of integer;
     w,k,m,j,i,h,f:integer;
begin
  assign(input,'b.in');
  assign(output,'b.out');
  reset(input);rewrite(output);
  k:=1;h:=0;
  for i:=1 to n do
    begin
      b[i]:=0;
      for j:=1 to n do
        begin
          read(a[i,j]);
          b[i]:=b[i]+a[i,j];
        end;
      if (b[i] mod 2=1)
         then begin
                inc(h);
                if k=1 then k:=i
                       else w:=i;
              end;
     end;
     if h>2 then
       begin
         writeln('NO SOLUTION');
         exit;
       end;
     write(k);
     repeat
       i:=1;f:=b[i]; f:=a[k,i];
       while ( (b[i]=1) or (f=0)and(i<=n)) do begin inc(i);f:=a[k,i];end;
       if i<=n then begin
         write('--->',i);
         a[k,i]:=0;
         a[i,k]:=0;
         b[k]:=b[k]-1;
         b[i]:=b[i]-1;
         k:=i;
         end;
    until i=n+1;
    writeln('--->',w);close(input);close(output);
end.
输出文件0 1 0 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 0  
朋友们好 
这个程序在TP里面呢感运行,但是在FREEPASCAL里面却不行,请帮忙找找原因

回复列表 (共7个回复)

沙发

我的fp编译通过,你的程序解释一下好吗?
一笔画:
任取一个起点,开始下面的步骤 
如果该点没有相连的点,就将该点加进路径中然后返回。 
如果该点有相连的点,就列一张相连点的表然后遍历它们直到该点没有相连的点。(遍历一个点,删除一个点) 
处理当前的点,删除和这个点相连的边, 在它相邻的点上重复上面的步骤,把当前这个点加入路径中. 
  procedure Main(head:integer);
  var i:integer;
  begin
    for i:=1 to n do
    if g[head,i]>0 then
        begin
          dec(g[head,i]);dec(g[i,head]);
          Main(i);
        end;
    inc(k);p[k]:=head;
  end;

板凳

不是那么简单的, 比如这个图:

4------5       7-------8
|      |       |       |
|      |       |       |
|      |       |       |
3------1-------2-------6


如果你直接把1---2加进去的话, 那么你就不可能画出来了, 算法很复杂的.

3 楼

ei??对哦!那应该怎么做呀???

4 楼

像1--2这种边称做"桥", 实际处理时先处理非桥边, 把非桥边处理完了之后, 原来的桥也就变成非桥边了.

大概就是这样, 以上

5 楼

??说清楚点好吗?什么叫做桥?起点和终点?

6 楼

如果你把1--2这条边去掉, 那么整个图将不连通.
一条边为桥的充要条件是去掉这条边会使整个图由连通变为不连通

以上

7 楼

哦谢谢,那请问一个图可能有多个桥吗?处理时,是不是先把桥删掉,然后能用我那个方法处理么?
如果具体算法,请给一下,谢谢!

我来回复

您尚未登录,请登录后再回复。点此登录或注册