题解

44 条题解

  • 0
    @ 2009-11-09 19:10:47

    program p1626;

    type shu=array[1..1001]of integer;

    var n,m,i,j,x,y,k,s,ps:integer;

    a:array[1..1001,1..1001]of boolean;

    p,pp,ppp:shu;

    d:boolean;

    procedure sou(x,i:integer; g:shu);

    var j,k:integer;

    begin

    g[x]:=i;

    for j:=1 to n do

    if a[x,j] then

    begin

    if j=i then

    begin

    for k:=1 to n do p[k]:=g[k];exit;

    end;

    if g[j]i then sou(j,i,g);

    end;

    end;

    begin

    readln(n,m);

    for i:=1 to m do

    begin

    readln(x,y); a[x,y]:=true;

    end;

    for i:=1 to n do p[i]:=i;

    for i:=1 to n do

    sou(i,i,p);

    i:=1;

    for k:=1 to n do for i:=1 to n do for j:=1 to n do

    a:=a or ((a)and(a[k,j]));

    for i:=1 to n do inc(pp[p[i]]);

    for i:=1 to n do if pp[i]>1 then inc(s);

    writeln(s);

    for i:=1 to n do

    if pp[i]>1 then

    begin

    d:=true;

    for j:=1 to n do

    if ij then

    if a[j,i] then d:=true

    else d:=false;

    if d then

    begin

    for j:=1 to n do

    if p[j]=i then begin inc(ps); ppp[ps]:=j end;

    for j:=1 to ps do

    if j=1 then write(ppp[j]) else write(' ',ppp[j]);

    writeln; halt;

    end;

    end;

    writeln('-1');

    end.

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案错误...程序输出比正确答案长

    ├ 测试数据 07:答案错误...程序输出比正确答案长

    ├ 测试数据 08:答案错误...程序输出比正确答案长

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:运行超时...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:50 有效耗时:0ms

    哪位大侠帮帮忙看一下哪里错了

  • 0
    @ 2009-10-27 21:19:50

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    好题 啊 强连通啊 我没学过

  • 0
    @ 2009-10-23 14:55:09

    Accepted 有效得分:100 有效耗时:0ms

    诧异了,我还不懂什么是缩点.....居然就白痴两次dfs一次过了.....

    话说这个开头不是《爱因为在心中》吗,好怀念啊,这是我们初中大合唱的歌曲啊T^T

  • 0
    @ 2009-10-21 17:47:38

    郁闷。。。。。。。。。。

    c1忘写了。。。。。。。。。

    90分 n次。。。。。。。。。

  • 0
    @ 2009-10-20 23:43:49

    貌似又些麻烦了……

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-07 11:58:06

    。。。我的AC率啊 &=.=&

    第一遍(比赛的时候)

    70.

    1点错

    2点超时

    Floyd做的

    现在

    第二遍

    Dfs.90.一点错。

    第三遍

    Dfs.80.2点错。格式错误/运行超时。

    第四遍

    以为是评测机的错误。。再提交一遍。。老样子。。

    第五遍

    AC..

  • 0
    @ 2009-10-05 00:08:14

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案错误...程序输出比正确答案长

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:90 有效耗时:0ms

    那位神牛知道为什么

  • 0
    @ 2009-10-04 22:19:28

    好多细节...

    我看来还是很沙茶的说...



    如果某个爱心天使被其他所有人【或!!】爱心天使所爱则请输出这个爱心天使是由哪些人构成的

  • 0
    @ 2009-09-21 17:55:15

    飘过~~~

    并查集A的,效率略微慢了点...

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 588ms

    ├ 测试数据 10:答案正确... 369ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:957ms

  • 0
    @ 2009-09-14 18:43:58

    爱心天使被其他所有人“和”爱心天使所爱

    爱心天使被其他所有人“或”爱心天使所爱

    到底是和还是或

  • 0
    @ 2009-09-04 17:24:03

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    第一次写Kosaraju,写的太墨迹了,还好秒杀了

  • 0
    @ 2009-08-31 12:06:31

    先缩强连通,然后对于点数量>=2的染白色否则染黑色。然后对于每个白色检查是否有白色指向这个点或者所有点是否都对其有边。

  • 0
    @ 2009-08-27 00:15:46

    没什么好说的。第一问求强连通分支,Kosaraju算法和tarjan算法皆可。第二问缩点,然后用floyd也行,dfs也行,按照题目描述判断就行。我判断的地方貌似有一点是n^3的,竟然也秒杀。数据弱……

    做这题真是太郁闷了。

    学习着写了tarjan算法,结果出现了这种情况

    第一次:

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:运行超时|格式错误...

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:90 有效耗时:0ms

    第二次:

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    搞什么,大数据秒杀,巨小的数据超时。完全一样的程序,同一个评测器,30s后重交,AC……

    欺负我第一次写tarjan?

  • 0
    @ 2009-08-26 16:36:25

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 196ms

    ├ 测试数据 10:答案正确... 165ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:361m

    floyd居然能过……就是慢了点………………还不如写个dfs呢……

    正向DFS+反向DFS=求强连通分量

    每个强连通分量反向DFS时若能到达所有节点就是被所有人爱。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 88ms

    ├ 测试数据 10:答案正确... 41ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:129ms

    dfs版也没秒杀。。为啥?是不是邻接矩阵慢?

  • 0
    @ 2009-08-25 21:38:33

    OO═══∩═══OO

        ╭╬╮         ◢

    -▁╭▅▇□□█▇▆▅▄▃▂▁(╳)█╮

      ╰═▃_专机来顶▁∠════▔▔▔ 

      ╙O ╙O!↓

  • 0
    @ 2009-08-25 16:21:19

    边可以这样改

    for i:=1 to m do

    with edge[i] do

    begin

    v1:=father[v1];

    v2:=father[v2];

    end;

    之后再将所有不重复边抽取到另一个edge数组

    另外,测评时莫名其妙地超时,交多次就0ms了.......

  • 0
    @ 2009-08-24 15:39:43

    dfs+反方向边bfs

    找环(强连通分量)

    缩成一点

    floyed

    求第二问

    1次ac!!!!!!!!!!!

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-08-23 22:40:41

    tmd,交了有10遍……

    先求强连通分量,再找度为0的强连通分量,如果只有一个且包含点数大于1,那么把所有边取反,从这个分量中的点BFS,如果能到所有点,就符合要求

  • 0
    @ 2009-08-23 22:21:58

    囧 一直以为只有两个人才能变成一个天使..

信息

ID
1626
难度
6
分类
图结构 | 强连通分量 点击显示
标签
(无)
递交数
1619
已通过
444
通过率
27%
被复制
2
上传者