Đề bài:
Thuật toán:
- (đang cập nhập)
Code:
const fi='';//stone1.inp'; fo='';//stone1.out'; maxn=403; maxm=403; type arr1 = array[1..maxn] of longint; var link,head,ke : array[-maxm..maxm] of longint; f,deg : array[1..maxn] of longint; i,j,n,m,k : longint; st : array[1..maxn,1..maxn] of longint; top : array[1..maxn] of longint; a : array[1..maxn,1..maxn] of boolean; cx : array[1..maxn] of boolean; procedure add(i,u,v : longint); begin link[i] := head[u]; head[u] := i; ke[i] := v; end; procedure enter; var u,v,i : longint; begin assign(input,fi);reset(input); read(n); for i := 1 to n do begin read(u,k); for j:=1 to k do begin read(v); if a[u,v] = false then begin a[u,v] := true; inc(deg[u]); end; if a[v,u] = false then begin a[v,u] := true; inc(deg[v]); end; end; end; close(input); end; procedure push(i,x : longint); begin inc(top[i]); st[i,top[i]] := x; end; procedure swap(var x,y : longint); var tg : longint; begin tg:=x;x:=y;y:=tg; end; procedure qs(l,r : longint; var a : arr1); var i,j,x : longint; begin i :=l;j:=r; x := a[(l+r) div 2]; repeat while a[i] > x do inc(i); while a[j] < x do dec(j); if i<=j then begin swap(a[i],a[j]); inc(i);dec(j); end; until i>j; if i<r then qs(i,r,a); if j>l then qs(l,j,a); end; procedure dfs(u : longint); var i,v,s : longint; begin cx[u] := false; if deg[u] <= 1 then begin f[u] := 1; exit; end; for v := 1 to n do if a[u,v] then if cx[v] then begin dfs(v); push(u,f[v]); end; qs(1,top[u],st[u]); s := st[u,1]; v := st[u,1]-1; for i:= 2 to top[u] do if v < st[u,i] then begin s := s + (st[u,i]-v); v := v + (st[u,i]-v); v := v - 1; end else v := v-1; f[u] := s; end; procedure process; begin fillchar(cx,sizeof(cx),true); dfs(1); end; procedure print; begin assign(output,fo);rewrite(output); writeln(f[1]); close(output); end; begin enter; process; print; end. |
BÌNH LUẬN MỚI