四维博客-ʩ

四维博客-ʩ

一直被超越,从未被模仿。

题解 U21238 【飞行的植物大炮】

posted on 2018-03-14 22:52:51 | under 题解 |

题干

  首先,我们可以看看这个样例,根据样例画一个矩阵,如下所示: $$\quad\;\;\;\begin{matrix}{}1&2&3&4&5&6\\\end{matrix}$$ $$\begin{array}{}1\\2\\3\\4\\5\\6\\\end{array}\left(\begin{matrix}{}0&1&1&1&0&0\\1&0&1&0&1&0\\1&1&0&0&1&1\\1&0&0&0&0&0\\0&1&1&0&0&1\\0&0&1&0&1&0\\\end{matrix}\right)$$   其中, $1$ 表示两个结点之间有边, $0$ 表示无边。当然你也可以用 $True$ 和 $False$ 来表示,只不过可能要麻烦些。在程序中,我们可以用一个二维数组 $G$ 把这个矩阵存储起来。

  接下来只要按照深度优先搜索的思路去把这个图进行遍历,大部分不需要具体的说明了。代码如下:

var
  n,m,i,j,a,b,sum:longint;
  g:array[1..1000,1..1000]of 0..1;
  f:array[1..1000]of boolean;
procedure dfs(i:longint);
var
  j:longint;
begin
  f[i]:=true;
  for j:=1 to n do
    if (g[i,j]=1)and(f[j]=false) then dfs(j);
end;
function check:boolean;
begin
  for i:=1 to n do if f[i]=false then exit(true);
  exit(false);
end;
begin
  readln(n,m);
  for i:=1 to m do
  begin
    readln(a,b);
    g[a,b]:=1; g[b,a]:=1;
  end;
  f[1]:=true;
  dfs(1);
  while check do
    for i:=1 to n do
      if f[i]=false then begin inc(sum); dfs(i); end;
  writeln(sum);
end.

  代码中有一个函数 $\text{“}check\text{”}$ ,它的作用是:检查是否已经将一个连通子图遍历完毕。若已经遍历完了一个连通子图,则换一个未被访问过的源点继续搜索。一旦换了源点,就把 $sum$ 加 $1$ 。 $sum$ 的最终结果就相当于题目中植物大炮的飞行次数。