题解

34 条题解

  • -1
    @ 2009-11-02 19:31:15

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

    连通分量=1时第二问=0

    Kosaraju学起来好快~

  • -1
    @ 2009-10-31 23:30:13

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

    这不是USACO的原题么。。直接强连通分量阿。。

  • -1
    @ 2009-10-29 11:03:28

    求强连通的基础题

    对于n

  • -1
    @ 2009-10-17 17:23:44

    我用floyd过的

    一遍

  • -1
    @ 2009-10-14 18:58:31

    7楼:

    反例:

    12

    34

    R=C=0

  • -1
    @ 2009-09-27 19:11:10

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

    囧 我交了三次

  • -1
    @ 2009-09-27 16:21:10

    交的时候卡了一下 结果通过里面我就占了两个名字 o(╯□╰)o

    hydralisk fjxmlhx Shouler_Akai ghostmea 陈亮宇 陈亮宇 

  • -1
    @ 2009-09-10 19:14:36

    强连通缩点为拓扑图后。

    设入度为0点数为x

    出度为0点数为y

    下面第一问:

    答案至少为x,答案为x时可行。

    下面第二问:

    若只有一个点,则答案为0;否则答案至少为max(x,y),然后考虑构造方法:

    对于多个连通快

    设每个连通块入度为0的点只有1个

    设每个连通块出度为0的点为k个

    设k>1

    则k-1个点连向自己连通快入度为0的点

    剩下一个点连到其他连通块的入度为0的点

    其他情况类似,不一一列举.所以当点>1时,答案为max(x,y)

  • -1
    @ 2009-09-28 12:47:07
  • -1
    @ 2009-08-27 11:33:54

    easy..

    一次AC。

  • -1
    @ 2009-08-14 20:09:02

    我用了个很简单的方法

    设入度为0的点有R个

    出度为0的点有C个

    A:max(R,1);

    B:max(R,C);

    可是第7个点错了

    谁能说下错在哪里 小弟不胜ORZ

  • -1
    @ 2009-08-04 11:12:03

    第二小问,要是有分成好几块的话该怎么处理啊?

    要是一块就简单了...

    只拿了82分丫丫

  • -1
    @ 2009-08-02 11:00:59

    Orz 1s……

    求强连通分量我还是喜欢写Tarjan算法,毕竟只要一次DFS……

  • -2
    @ 2009-11-01 17:42:44

    先将强连通分量缩成点,然后再求入度和出度为0的强连通分量,第一问输出入度为0的强连通分量,第二问输出入度和出度为0较大的那个,ps。如果只有一个强连通分量则输出1 我很懒直接floyd的(Kosaraju算法比较优秀)

    const maxn = 101;

    var

    a : array [0..maxn,0..maxn] of boolean;

    lt : array [0..maxn] of longint;

    v , ru , chu : array [0..maxn] of boolean;

    n , tot , rud , chud : longint;

    procedure init;

    var i , x , tot : longint;

    begin

    readln(n); fillchar(a,sizeof(a),0); fillchar(v,sizeof(v),0); ru := v; chu := v;

    for i := 1 to n do

    begin

    read(x); while x 0 do begin a := true; read(x); end;

    readln;

    end;

    end;

    procedure main;

    var i , j , k : longint;

    begin

    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

    if not v[i] then

    begin

    inc(tot); lt[tot] := i; v[i] := true;

    for j := 1 to n do if a and a[j,i] then v[j] := true;

    end;

    for i := 1 to tot do

    for j := 1 to tot do

    if i j then

    begin

    if a[lt[i],lt[j]] then chu[i] := true;

    if a[lt[j],lt[i]] then ru [i] := true;

    end;

    rud := 0; chud := 0;

    for i := 1 to tot do

    begin

    if not ru [i] then inc( rud);

    if not chu[i] then inc(chud);

    end;

    writeln(rud);

    if tot = 1 then begin writeln(0); exit; end;

    if chud > rud then writeln(chud) else writeln(rud);

    end;

    begin

    init;

    main;

    end.

信息

ID
1595
难度
5
分类
图结构 | 强连通分量贪心 点击显示
标签
递交数
1034
已通过
333
通过率
32%
被复制
2
上传者