http://acm.pku.edu.cn/JudgeOnline/problem?id=1236
Задача Межшкольная сеть
Некоторые школы связаны компьютерной сетью. Между школами заключены соглашения: каждая школа имеет список школ-получателей, которым она рассылает программное обеспечение всякий раз, получив новое программное обеспечение (извне сети или из другой школы). При этом, если школа В есть в списке получателей школы А, то школа А может и не быть в списке получателей школы В.
Требуется написать программу, определяющую минимальное количество школ, которым надо передать по экземпляру нового программного обеспечения, чтобы распространить его по всем школам сети в соотвествии с соглашением (подзадача А).
Кроме того, надо обеспечить возможность рассылки нового программного обеспечения из любой школы по всем остальным школам. Для этого можно расширять списки получателей некоторых школ, добавляя в них новые школы. Требуется найти минимальное суммарное количество расширений списков, при которых программное обеспечение из любой школы достигло бы всех остальных школ (подзадача В). Одно расширение означает добавление одной новой школы-получателя в список получателей одной из школ.
Технические условия. Входные данные: Первая строка содержит целое число N - количество школ в сети (2 <= N <= 100). Школы нумеруются первыми N положительными целыми числами. Каждая из следующих N строк задает список получателей. Строка i+1 содержит номера получателей i-й школы. Каждый такой список заканчивается нулем. Пустой список содержит только нуль.
Выходные данные: Ваша программа должна вывести две строки. Первая строка должна содержать одно положительное целое число - решение подзадачи А. Вторая строка должна содержать решение подзадачи В.
Пример входных данных:
5
2 4 3 0
4 5 0
0
0
1 0
Пример выходных данных:
1
2
Обсуждение задачи
Для решения задачи требуется знание фундаментального математического понятия "отношение" и, соответственно, понятия "замкнутость отношения". Кратко рассмотрим их.
Бинарным отношение R двух множеств А и В называют подмножество прямого произведения А и В. Прямое (декартовое) произведение двух множеств А и В есть множество упорядоченных пар, в котором первый элемент каждой пары принадлежит А, а второй принадлежит В. Если А = В, то говорят, что R есть отношение на множестве А.
Отношение R обладает обычно рядом свойств. Так, оно обладает свойством транзитивности, если для любых элементов a, b, c, принадлежащих А, из a R b и b R c следует, что a R c. Словами это проговаривается так: если a и b находятся в отношении R и b и c находятся в отношении R, то пара a и c также находятся в отношении R.
Неформально говоря, замкнутость отношения относительно некоторого свойства означает, что многократное его применение не выводит нас за определенные границы. Задачу же нахождения по транзитивному отношению R отношения R*, обладающего свойством замкнутости, называют задачей замыкания, а отношение R* - транзитивным замыканием R.
Для более детального ознакомления с решением, базирующимся на данном подходе, рекомендуем всем желающим обратиться к книге Кирюхин В.М., Окулов С.М. "Методика решения задач по информатике. Международные олимпиады", - М.: БИНОМ. Лаборатория знаний, 2007. - 600 с.: ил., где этот подход применительно к этой задаче детально разобран на стр. 148-154.
Мы же приведем 2 других решения, одно из которых базируется на алгоритме Флойда-Уоршелла, а второе на понятии доминирующих множеств, с которыми рекомендуем разобраться самостоятельно.
var a,b,floyd,ad:array[1..100,1..100]of byte;
fdi,fde,di,de:array[1..100]of byte;
i,x,y,nr,min,nrcomp,nrext,j,k,l,m,n,nrctc:longint;
luate:set of byte;
bb:boolean;
ctc:array[1..100]of set of byte;
ss:string;
procedure dofloyd;
var i,j,k:byte;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if floyd[i,k]+floyd[k,j]=2 then floyd[i,j]:=1;
for i:=1 to n do
for j:=1 to n do
if a[i,j]=1 then
begin
inc(fdi[j]);
inc(fde[i]);
end;
end;
procedure calcctc;
begin
b:=a;
floyd:=a;
dofloyd;
a:=floyd;
for i:=1 to n do
for j:=1 to n do
if a[i,j]+a[j,i]=1 then
begin
a[i,j]:=0;
a[j,i]:=0;
end;
nrctc:=0;
luate:=[];
for i:=1 to n do
if not(i in luate) then
begin
inc(nrctc);
ctc[nrctc]:=[i];
for j:=1 to n do
if a[i,j]=1 then
ctc[nrctc]:=ctc[nrctc]+[j];
luate:=luate+ctc[nrctc];
end;
a:=b;
for i:=1 to nrctc do
for j:=1 to nrctc do
if i<>j then
for k:=1 to n do
if k in ctc[i] then
for l:=1 to n do
if l in ctc[j] then
if a[k,l]=1 then
ad[i,j]:=1;
end;
begin
readln(n);
nrcomp:=0;
for i:=1 to n do
begin
read(j);
while j<>0 do
begin
a[i,j]:=1;
inc(de[i]);
inc(di[j]);
read(j);
end;
end;
fillchar(ad,sizeof(ad),0);
calcctc;
for i:=1 to nrctc do
begin
di[i]:=0;de[i]:=0;
for j:=1 to nrctc do
if ad[i,j]=1 then inc(de[i]);
for j:=1 to nrctc do
if ad[j,i]=1 then inc(di[i]);
end;
k:=0;l:=0;
for i:=1 to nrctc do
if (di[i]=0)and(de[i]<>0)then inc(k);
for i:=1 to nrctc do
if (de[i]=0)and(di[i]<>0)then inc(l);
for i:=1 to nrctc do
if de[i]+di[i]=0 then begin inc(k);inc(l);end;
m:=k;
if l>k then k:=l;
if nrctc=1 then
k:=0;
writeln(m);
writeln(k);
end.Const MaxN=200; { max number of schools }
Type
GraphType=Array[1..MaxN,0..MaxN] Of 0..MaxN;
VertexSet=Set Of 1..MaxN;
Var
N :Word; { the number of schools }
G: GraphType; { representation of the network with graph G; }
{ G[p,0] is the number of edges outgoing from p }
{ the outgoing edges from p: (p, G[p,i]) 1<=i<=G[p,0]) }
Domin, { dominator set }
CoDomin: VertexSet; { codominator set }
NoDomins, { number of dominator elements }
NoCoDomins: 0..MaxN;{ number of codominator elements }
AnswerB: 0..MaxN; { solution of subtask B }
p: 0..MaxN;
Procedure ReadInput;
{ Global output variables: N, G }
Var i,p: Word;
Begin
ReadLn(N);
For i:=1 To N Do
G[i,0]:=0;
For i:=1 To N Do Begin
Read(p);
While p<>0 Do Begin
Inc(G[i,0]);
G[i,G[i,0]]:=p;
Read(p);
End;
ReadLn;
End;
End { ReadInput };
Procedure ComputeDomin(Const G: GraphType; Var D: VertexSet);
{ Computes a minimal dominator set D of graph G }
{ Global input variables: N }
Var
Dominated, Reachable: Set of 1..MaxN;
p: 1..MaxN;
Procedure Search(p:Word);
Var i: Word;
Begin
Exclude(D, p);
Include(Dominated, p);
For i:= 1 To G[p,0] Do
If Not (G[p,i] in Reachable) Then Begin
Include(Reachable,G[p,i]);
Search(G[p,i]);
End;
End { Search };
Begin { ComputeDomin }
D:=[];
Dominated:=[];
For p:=1 To N Do
If Not (p In Dominated) Then Begin
Reachable:=[p];
Search(p);
Include(D, p);
End;
End { ComputeDomin };
Procedure ComputeCoDomin(Const G: GraphType; Var CD: VertexSet);
{ Computes a minimal codominator set D of graph G }
{ Global input variables: N }
Var
GT: GraphType; { transposed graph of G }
p,q: 1..MaxN; i:Word;
Begin { ComputeCoDomin }
For p:=1 To N Do
GT[p,0]:=0;
For p:=1 To N Do { compute the transpose of the graph G in GT }
For i:=1 To G[p,0] Do Begin
q:=G[p,i];
Inc(GT[q,0]); GT[q,GT[q,0]]:=p;
End;
ComputeDomin(GT, CD) { computes CD, the dominator set of GT }
End;{ ComputeCoDomin }
Begin { Program }
ReadInput;
ComputeDomin(G,Domin);
ComputeCoDomin(G,CoDomin);
NoDomins:=0;
For p:=1 To N Do { count the number of elements in the set Domin }
If p In Domin Then Inc(NoDomins);
NoCoDomins:=0;
For p:=1 To N Do { count the number of elements in the set CoDomin }
If p In CoDomin Then Inc(NoCoDomins);
If (Domin=[1]) And (CoDomin=[1]) { strongly connected }
Then AnswerB:=0
Else If NoDomins > NoCoDomins
Then AnswerB:=NoDomins
Else AnswerB:=NoCoDomins;
WriteLn(NoDomins);
Writeln(AnswerB);
End.Ну и конечно же, решение на С++. Очень интересный и полезный алгоритм. Также рекомендуем разобраться самостоятельно.
#include <iostream>
using namespace std;
const int N=101;
int gMap[N][N],nMap[N][N];
int mapNo[N];
int connC;
int inC[N],outC[N];
bool vst[N];
int n;
int stack[N*N],sn;
void DFS1(int x)
{
vst[x]=true;
for(int i=1;i<=n;++i)
{
if(gMap[x][i] && ! vst[i])
DFS1(i);
}
stack[++sn]=x;
}
void DFS2(int x,int mark)
{
vst[x]=true;
mapNo[x]=mark;
for(int i=1;i<=n;++i)
{
if(gMap[i][x] && ! vst[i])
DFS2(i,mark);
}
}
void Korasaju()
{
int i,j;
for(i=1;i<=n;++i)
{
if(! vst[i])
DFS1(i);
}
memset(vst,false,sizeof(vst));
for(i=sn;i>=1;--i)
{
if(! vst[stack[i]])
DFS2(stack[i],++connC);
}
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
if(gMap[i][j] && mapNo[i]!=mapNo[j])
nMap[mapNo[i]][mapNo[j]]=true;
}
}
}
bool Read()
{
if(scanf("%d",&n)==EOF || n==-1)
return false;
for(int i=1,t;i<=n;++i)
{
while(scanf("%d",&t),t)
gMap[i][t]=true;
}
return true;
}
void Solve()
{
Korasaju();
memset(inC,0,sizeof(inC));
memset(outC,0,sizeof(outC));
int i,j;
for(i=1;i<=connC;++i)
{
for(j=1;j<=connC;++j)
{
if(nMap[i][j])
++outC[i],++inC[j];
}
}
int zeroIn=0,zeroOut=0;
for(i=1;i<=connC;++i)
{
if(inC[i]==0)
++zeroIn;
if(outC[i]==0)
++zeroOut;
}
printf("%d\n",zeroIn);
if(connC==1)
puts("0");
else
printf("%d\n",zeroIn>zeroOut ? zeroIn : zeroOut);
}
int main()
{
while(Read())
Solve();
return 0;
}