34 条题解
-
-1prince_hao LV 10 @ 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学起来好快~ -
-12009-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的原题么。。直接强连通分量阿。。 -
-12009-10-29 11:03:28@
求强连通的基础题
对于n -
-12009-10-17 17:23:44@
我用floyd过的
一遍 -
-12009-10-14 18:58:31@
7楼:
反例:
12
34
R=C=0 -
-12009-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囧 我交了三次
-
-12009-09-27 16:21:10@
交的时候卡了一下 结果通过里面我就占了两个名字 o(╯□╰)o
hydralisk fjxmlhx Shouler_Akai ghostmea 陈亮宇 陈亮宇
-
-12009-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) -
-12009-09-28 12:47:07@
-
-12009-08-27 11:33:54@
easy..
一次AC。
-
-12009-08-14 20:09:02@
我用了个很简单的方法
设入度为0的点有R个
出度为0的点有C个
A:max(R,1);
B:max(R,C);可是第7个点错了
谁能说下错在哪里 小弟不胜ORZ -
-12009-08-04 11:12:03@
第二小问,要是有分成好几块的话该怎么处理啊?
要是一块就简单了...
只拿了82分丫丫 -
-12009-08-02 11:00:59@
Orz 1s……
求强连通分量我还是喜欢写Tarjan算法,毕竟只要一次DFS…… -
-22009-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;
beginreadln(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;
beginfor 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.