图论的实际应用之四 割点 (300分)

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-16

• #1

美英联军在乌姆盖斯尔和巴格达之间的N个城镇建立了临时的有线通讯中心.每两个通讯中心之间有可能可以直接通讯,也可能无法直接通讯,但通过其他通讯中心肯定能够实现间接的通讯.矩阵a[n, n]表示n个通讯中心之间的联系情况,a[i, j]=1表示i和j通讯中心可以直接联系,a[i, j]=0表示i和j通讯中心之间无法直接联系,显然a[i, j]=a[j, i].试为伊军编一程序,找出是否存在这样的可能:只要伊军拿下其中的一个通讯中心,就可以破坏除该城外的其他通讯中心之间的通讯.如果可能,指出所有可行解.
上一题:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1953299
下一题:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1958995

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-16

• #2

好像DFS一次就够了

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-17

• #3

按照DFS的顺序建立一颗K叉树，凡是有两个以上子节点的节点即为割点

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-17

• #4

徒说无宜.

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-17

• #5

呵呵，要程序啊，等一会儿吧

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-17

• #6

ft,方法又错了

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #7

用N次DFS行不行啊？

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #8

用N次肯定可以,
但实际上用1次就可以.

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #9

枚举去掉一个顶点，然后用封包传递算法看看剩下的是不是个连通图

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #10

我想一次那个想得实在头疼

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #11

这个方法行不行啊？
我是说时间复杂度的要求能不能通过

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #12

呵呵，很难.

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #13

两本书上都讲得不清楚，还和别的问题混着讲，看着就头晕

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #14

呵呵，你不会总是对着我的问题再去看书的吧.
应该把该看的书都看了,以后碰到问题不就得心应手了,何况对你来说,比赛在即.

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #15

说实话，NOI图论考得不多

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #16

不是考的不多,而是很多题目选手们想不到用图论去解.

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-01

• #17

一半人是想不到，而另一半人是通常有更高效的解法

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #18

终于想通了！以下程序在Win2K+TP7.0下测试通过。
const maxn=20;
s=1;
type node=record
dfn,low,flag:integer;
end;
var g:array[1..maxn,1..maxn] of 0..1;
p:array[1..maxn] of node;
r:array[1..maxn] of 0..1;
i,j,n,dfn:integer;
function low(x:integer):integer;
var i,j,k:integer;
begin
dfn:=dfn+1;
p[x].dfn:=dfn;
p[x].low:=dfn;
p[x].flag:=1;
if x=s then
begin
j:=0;
for i:=1 to ndo
if (g[x,i]=1) and (p.flag=0) then
begin
j:=j+1;
k:=low(i);
end;
if j>1 then
r[x]:=1;
end else
begin
j:=0;
for i:=1 to ndo
if g[x,i]=1 then
if p.flag=0 then
begin
k:=low(i);
if k>=p[x].dfn then
j:=j+1;
if p[x].low>k then
p[x].low:=k;
end
else
if p[x].dfn>p.dfn then
if p[x].low>p.dfn then
p[x].low:=p.dfn;
if j>0 then
r[x]:=1;
end;
p[x].flag:=2;
low:=p[x].low;
end;

begin
fillchar(p,sizeof(p),0);
read;
for i:=1 to ndo
for j:=1 to ndo
read(g[i,j]);
dfn:=0;
fillchar(r,sizeof(r),0);
i:=low(1);
for i:=1 to ndo
if r=1 then
write(i,' ');
writeln;
end.

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #19

因为我没有参考书上的源程序和算法流程，只看了题目分析，所以可能有没考虑周全的地方，麻烦您多测试一下。

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #20

呵呵，大差不差，我也没有什么有针对性的测试数据。
看看你的程序结构，已经把根结点单独处理了，这是求割顶的关键所在。